MINT lernen

Formale und natürliche Sprache

Warum ein Compiler bei einem fehlenden Semikolon streikt — und ein Mensch den Satz trotzdem versteht.

1

Alphabet, Wort, Sprache

Automaten lesen Wörter und entscheiden, ob sie dazugehören. Jetzt geht es um die Sprachen selbst — und ihre Bausteine.

  • Alphabet Σ:endliche, nichtleere Menge von Zeichen, z. B. \(\Sigma=\{a,b\}\) oder \(\Sigma=\{0,1\}\).
  • Wort:endliche Folge von Zeichen aus Σ, z. B. abba.
  • Länge |w|:Anzahl der Zeichen: \(|\texttt{abba}|=4\); \(|w|_a\) zählt nur die a.
  • Leeres Wort ε:das Wort ohne Zeichen, \(|\varepsilon|=0\).
  • Verkettung:\(uv\) schreibt v hinter u; \(a^3=aaa\).
  • Präfix, Suffix:Anfangs- bzw. Endstück eines Worts; ein Teilwort ist ein zusammenhängendes Stück.
  • \(\Sigma^*\), \(\Sigma^n\):alle Wörter über Σ (mit ε) bzw. alle Wörter der Länge n.
  • Formale Sprache:jede Teilmenge \(L\subseteq\Sigma^*\), z. B. \(L=\{a^nb^n\mid n\ge 0\}\).

Lege das Lineal an ein Wort an: Ziehe die beiden Marken (oder wähle sie mit Tab und verschiebe sie mit ←/→). Erfülle die drei Messaufträge und wechsle dann mit „Beispiele“ zum nächsten Wort.

Das Wort-Lineal

    Halte fest: Die Länge zählt Zeichen, nicht Zentimeter. Liegt das Lineal am Anfang an, misst es ein Präfix, am Ende ein Suffix. Bei Länge 0 misst es das leere Wort ε — es steckt in jedem Wort, an jeder Stelle.

    Herleitung:

    \(|\Sigma| = \textcolor{#2c5fb5}{k}\)
    Alphabet
    Das Alphabet hat \(k\) Zeichen, z. B. \(\Sigma=\{a,b\}\) mit \(k=2\).
    \(\textcolor{#2c5fb5}{k}\)
    1. Stelle
    Für das erste Zeichen gibt es \(k\) Möglichkeiten.
    \(\textcolor{#2c5fb5}{k}\cdot \textcolor{#e79a3a}{k} = k^2\)
    2. Stelle
    Jede Wahl der ersten Stelle lässt sich mit jeder der zweiten kombinieren.
    \(\underbrace{k\cdot k\cdot\ldots\cdot k}_{n\text{-mal}} = k^n\)
    n Stellen
    Bei jeder weiteren Stelle vervielfacht sich die Anzahl um \(k\).
    \(|\Sigma^n| = k^n,\qquad |\{a,b\}^3| = 2^3 = 8\)
    Ergebnis
    Die 8 Wörter der Länge 3 über \(\{a,b\}\): aaa, aab, aba, abb, baa, bab, bba, bbb. Für \(n=0\) gibt es genau ein Wort: ε.
    2

    Natürlich oder formal?

    • Natürliche Sprache:gewachsen (Deutsch, Englisch), Regeln unvollständig, viele Ausnahmen.
    • Mehrdeutig:„Er sieht den Mann mit dem Fernglas.“ — wer hält das Fernglas?
    • Formale Sprache:künstlich; exakte Regeln legen genau fest, welche Wörter dazugehören.
    • Syntax:Regeln für den Aufbau — welche Zeichenfolgen korrekt gebildet sind.
    • Semantik:Bedeutung eines korrekt gebildeten Worts.
    • Beispiele:Programmiersprachen, Datumsangaben TT.MM.JJJJ, Kfz-Kennzeichen, E-Mail-Adressen.
    WortSyntaxSemantik
    int x = 5 +;fehlerhaft— (Compiler lehnt ab)
    x = x / 0;korrektDivision durch 0: Laufzeitfehler
    30.02.2027korrektkein existierender Tag
    „Farblose grüne Ideen schlafen wütend.“korrektohne sinnvolle Bedeutung
    Merke

    Formale Sprache: Ein Alphabet Σ ist eine endliche, nichtleere Zeichenmenge, ein Wort eine endliche Zeichenfolge über Σ (ε: leeres Wort). Eine formale Sprache ist eine Teilmenge \(L\subseteq\Sigma^*\). Es gibt \(|\Sigma|^n\) Wörter der Länge n. Die Syntax legt fest, welche Wörter zu L gehören, die Semantik, was sie bedeuten.

    3

    Allgemeine Hinweise

    ε ist kein Zeichen

    ε gehört nicht zu Σ, sondern ist ein Wort. \(\{\varepsilon\}\) ist eine Sprache mit einem Wort, \(\emptyset\) eine Sprache ganz ohne Wörter.

    Σ endlich, Σ* unendlich

    Schon \(\Sigma=\{a\}\) liefert unendlich viele Wörter: ε, a, aa, aaa, … — jedes einzelne ist aber endlich lang.

    Korrekt heißt nicht sinnvoll

    Die Syntax prüft nur die Form. Ob ein syntaktisch korrektes Wort auch etwas Sinnvolles bedeutet, ist eine Frage der Semantik.

    Videos