Natürliche Sprache ist bedeutungsoffen und vom Zusammenhang abhängig. Formale Sprachen setzen enger an: Sie beschreiben einen Zeichenvorrat, Regeln und zulässige Zeichenfolgen.
Q3.1 startet die Formalsprachen-Reihe als begriffliche Grundlage: Sprache und formale Grammatik werden erzeugend beschrieben. Q3.2 fragt anschließend, wie endliche Automaten solche Sprachmuster erkennen. Q3.3 erweitert die Sicht auf geschachtelte Strukturen und Kellerautomaten.
Der rote Faden ist deshalb: Zeichen werden zu formalen Wörtern, Regeln erzeugen zulässige Wörter, und Darstellungen wie Ableitungsbaum, Syntaxdiagramm oder Chomsky-Hierarchie ordnen dieselbe formale Sprache ein, ohne neue Hauptachsen zu eröffnen.
Die Begriffe bauen aufeinander auf: Aus einzelnen Zeichen wird ein Alphabet, aus dem Alphabet entstehen formale Wörter, und eine formale Sprache wählt aus allen möglichen Wörtern nur die zulässigen aus. Eine formale Sprache ist eine Menge zulässiger Wörter über einem Alphabet.
A, 0 oder ;.Beim Zugangscode kann Σ = {A, B, 0, 1} gewählt werden. Dann sind A101, B011, A001 und B10 Wörter über Σ, aber nicht jedes davon gehört zur zulässigen formalen Sprache L. C101 ist in diesem Modell nicht einmal ein Wort über Σ, weil C nicht im Alphabet liegt.
Anschluss an Q3.2: In Q3.1 beschreiben wir solche zulässigen Wörter erzeugend mit Grammatikregeln. In Q3.2 entscheidet ein Akzeptor für ein gegebenes Wort, ob es zu L gehört.
L als Teilmenge von Σ*. Was lernt man? Nicht jedes Wort über Σ gehört zur formalen Sprache.
Syntax und Semantik gehören zusammen, aber sie beantworten unterschiedliche Fragen: Syntax beschreibt die formale Gestalt zulässiger Zeichenfolgen, Semantik beschreibt Bedeutung oder Interpretation. Formale Grammatiken in Q3.1 beschreiben zunächst vor allem Syntax.
In Programmen führt bereits ein kleines Strukturproblem zu Fehlern, zum Beispiel eine fehlende schließende Klammer oder ein falsches Trennzeichen.
Mini-Befehlssprache für einen Zeichenroboter: F10;, R90;, L5;. Syntaktisch gültig ist hier die Form „Buchstabe + Zahl + Semikolon“.
Lernpunkt: Die Mini-Befehlssprache zeigt, dass eine formale Grammatik die erlaubte Gestalt einer Zeichenfolge festlegen kann.
Ein Ausdruck kann syntaktisch korrekt sein, aber inhaltlich unpassend oder sinnlos. Alltagssprache und Programmlogik zeigen diesen Unterschied gleichermaßen.
Auch in der Mini-Befehlssprache kann ein formal korrekter Befehl semantisch problematisch sein, etwa wenn der Zeichenroboter durch F10; gegen eine Wand fahren würde oder ein Winkel im Kontext nicht erlaubt ist.
Lernpunkt: Eine syntaktisch korrekte Zeichenfolge ist Voraussetzung für Verarbeitung, aber noch nicht automatisch semantisch sinnvoll.
Eine formale Grammatik beschreibt nicht nur einzelne Regeln, sondern ein geordnetes Erzeugungssystem für formale Sprachen. Sie legt fest, wie aus einem gemeinsamen Startsymbol Schritt für Schritt zulässige Wörter entstehen können.
Die erzeugende Sicht fragt: Welche Wörter über dem Alphabet lassen sich nach den Regeln herstellen? Die erkennende Sicht aus Q3.2 fragt später: Akzeptiert ein Automat ein gegebenes Wort?
G = (N, T, P, S)
Eine Produktion beschreibt, welcher Platzhalter durch welche Folge von Symbolen ersetzt werden darf. Dabei können auf der rechten Seite Terminale und Nicht-Terminale stehen; erst am Ende bleiben nur noch Terminale übrig.
Als kompakte Variante des Zugangscode-Kontexts:S → A X | B XX → 0 Y | 1 YY → 0 Y | 1 Y | 1
Die Grammatik ist bewusst didaktisch vereinfacht: Sie zeigt die Erzeugungsidee, modelliert aber noch nicht alle Zusatzbedingungen des Zugangscode-Kontexts, zum Beispiel „kein 00“.
Damit ist klar trennbar, was im Prozess nur Hilfssymbol ist (Nicht-Terminal) und was im Ergebniswort stehen darf (Terminal).
G = (N, T, P, S). Was lernt man? Jede Komponente hat eine eigene Rolle im Erzeugungsprozess.Eine Ableitung ist ein Weg durch den Regelraum einer formalen Grammatik. Sie beginnt beim Startsymbol S; jedes Zwischenergebnis darf noch Nicht-Terminale enthalten. Erst wenn nur noch Terminale vorhanden sind, ist ein Wort über dem Alphabet erzeugt.
P = { S → aA, A → bA, A → b }
S → aA → abA → abb
Das Minimalbeispiel abb macht den Prozess gut sichtbar: Aus S entsteht zuerst ein Zwischenausdruck, dann werden die Platzhalter weiter ersetzt, bis keine Nicht-Terminale mehr vorkommen.
Anwendungstransfer mit vereinfachter Zugangscode-Grammatik:S → A X → A1 Y → A10 Y → A101. Der Zugangscode nutzt dieselbe Ableitungsidee, nur mit einem Anwendungskontext statt mit den abstrakten Symbolen a und b.
Σ kann aus S durch Produktionen entstehen.S zu diesem Wort.S abgeleitet werden können.Die Perspektive lässt sich auch umdrehen: Gegeben ist ein Wort wie A101, und die Analyse fragt, ob ein Ableitungsweg von S zu genau diesem Wort existiert.
Begriffsabgrenzung zu Q3.2: Eine formale Grammatik erzeugt Wörter in L(G); ein Automat erkennt Wörter, die zu seiner akzeptierten Sprache gehören.
S bis abb. Welcher Begriff? Ableitung als Erzeugungsweg. Was lernt man? Regelanwendungen erzeugen konkrete Wörter der formalen Sprache.Der Ableitungsbaum zeigt die hierarchische Erzeugungsstruktur einer Ableitung. Der Zugangscode-Kontext nutzt dieselbe Grundidee mit anderen Terminalsymbolen.
S, innere Knoten sind Nicht-Terminale und die Blätter sind Terminale. Welcher Begriff? Ableitungsbaum als Baumstruktur einer Ableitung. Was lernt man? Von links nach rechts gelesen ergeben die Blätter das Wort abb.Ein Syntaxdiagramm zeigt dagegen erlaubte Wege durch Regeln. In einer Mini-Befehlssprache kann ein gültiger Weg zum Beispiel das Konstrukt F10; ergeben.
Beide Darstellungen machen sichtbar, wie Regeln gültige Strukturen festlegen: Der Ableitungsbaum betont die hierarchische Erzeugung, das Syntaxdiagramm den erlaubten Pfad durch die Struktur.
REPEAT 3 { ... } mit verschachtelten Blöcken hinzukommen, reicht eine rein reguläre Beschreibung oft nicht mehr aus.S → aSb | ab erzeugt Wörter der Form a^n b^n.
Die Chomsky-Hierarchie ordnet Sprachklassen nach Ausdrucksstärke. Sie ist hier vor allem eine Landkarte: Sie zeigt, welche Regelarten zu welchen Sprachklassen und Erkennungsmodellen passen.
Die Grafik zeigt die Klassen als geschachtelte Mengen. Typ 0 ist am wenigsten eingeschränkt, Typ 3 ist am stärksten eingeschränkt. Von Typ 0 zu Typ 3 werden die Produktionsregeln also enger, dafür werden die passenden Modelle einfacher.
Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0 beschreibt eine echte Ausdrucksstärke-Ordnung.
Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0
Das Werkzeug macht den Q3.1-Lernweg praktisch erfahrbar: Eine formale Sprache wird zuerst als Menge zulässiger Wörter über einem Alphabet und als erzeugende Grammatik betrachtet.
Σ zulässig sind.G erzeugen.Σ* enthält alle endlichen Wörter über Σ; L ⊂ Σ* wählt daraus die zulässigen Wörter aus.G = (N, T, P, S) trennt die Rollen von Nicht-Terminalen, Terminalen, Produktionen und Startsymbol.L(G) ist die Menge aller Wörter, die aus S abgeleitet werden können.Damit ist die Brücke gebaut: Dieselbe Sprache, die hier durch Grammatik erzeugt wird, kann in Q3.2 durch endliche Automaten erkannt werden. Q3.3 zeigt anschließend, warum geschachtelte kontextfreie Strukturen zusätzlichen Stack-Speicher brauchen.