Mit Google fortfahren
Formale Grammatik: Regeln, Ableitung und Sprache
Eine formale Grammatik beschreibt mit eindeutigen Regeln, wie gültige Wörter einer formalen Sprache entstehen. Du startest mit einem besonderen Symbol und ersetzt schrittweise Symbole, bis nur noch Zeichen des gewünschten Wortes übrig sind.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Aus welchen vier Bestandteilen besteht eine Grammatik?
Eine Grammatik wird als Tupel geschrieben:
$$G=(N,T,P,S)$$
Formale Grammatik
Eine formale Grammatik besteht aus einer endlichen Menge von Nichtterminalen $N$, einer endlichen Menge von Terminalen $T$, einer endlichen Menge von Produktionen $P$ und einem Startsymbol $S$.
Die Bestandteile haben verschiedene Aufgaben:
| Bestandteil | Bedeutung | Beispiel |
|---|---|---|
| $N$ | Nichtterminale: noch zu ersetzende Hilfssymbole | $S$, $A$, $B$ |
| $T$ | Terminale: Zeichen, aus denen fertige Wörter bestehen | $a$, $b$, $0$, $1$ |
| $P$ | Produktionen: erlaubte Ersetzungen | $S\to aSb$ |
| $S$ | Startsymbol und Ausgangspunkt jeder Ableitung | $S$ |
Terminale und Nichtterminale dürfen sich nicht überschneiden: $N\cap T=\varnothing$. Das Startsymbol gehört zu den Nichtterminalen: $S\in N$. Auf der linken Seite einer allgemeinen Produktion muss mindestens ein Nichtterminal vorkommen.
Eine Produktion wie $S\to aSb$ bedeutet: Ersetze ein vorkommendes $S$ durch die Zeichenfolge $aSb$. Das Nichtterminal $S$ bleibt dabei erhalten und kann erneut ersetzt werden.
Nichtterminale kennzeichnen unfertige Stellen. Ein fertiges Wort enthält ausschließlich Terminale.
Wie entsteht ein Wort durch eine Ableitung?
Bei einer Ableitung wendest du nacheinander Produktionen an. Eine Regel darf an jeder passenden Stelle eingesetzt werden; eine allgemeine feste Reihenfolge gibt es nicht.
Gehört $\alpha\to\beta$ zu den Produktionen, darfst du in einem Kontext $x\alpha y$ den Teil $\alpha$ ersetzen:
$$x\alpha y\Rightarrow x\beta y$$
Der Pfeil $\Rightarrow$ steht für einen Ableitungsschritt. $\Rightarrow^*$ bedeutet: Es sind null oder mehr Schritte möglich.
Betrachte die Grammatik
$$G=(\{S\},\{a,b\},P,S)$$
mit den Regeln
$$S\to aSb\mid\varepsilon$$
Das Zeichen $\varepsilon$ bezeichnet das leere Wort, also eine Zeichenfolge ohne Zeichen.
Wir leiten aabb ab:
$$S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$$
- Mit $S\to aSb$ entsteht außen ein $a$ und ein $b$.
- Dieselbe Regel erzeugt ein zweites passendes Paar.
- Mit $S\to\varepsilon$ verschwindet das letzte Nichtterminal.
Das Ergebnis aabb enthält nur Terminale und ist damit ein fertiges Wort.
Die Ausdrücke $S$, $aSb$ und $aaSbb$ heißen Zwischenformen. Sie gehören noch nicht zur erzeugten Sprache, weil sie das Nichtterminal $S$ enthalten.
Welche Sprache erzeugt eine Grammatik?
$T^*$ bezeichnet alle endlichen Wörter über dem Terminalalphabet $T$, einschließlich $\varepsilon$. Die von $G$ erzeugte Sprache ist
$$L(G)=\{w\in T^*\mid S\Rightarrow^*w\}$$
Ein Wort gehört also genau dann zu $L(G)$, wenn es sich vom Startsymbol aus in endlich vielen Schritten ableiten lässt und am Ende nur Terminale enthält.
Für die Grammatik $S\to aSb\mid\varepsilon$ gilt:
$$L(G)=\{a^n b^n\mid n\in\mathbb N_0\}$$
Dabei bedeutet $a^n$: Das Zeichen $a$ wird $n$-mal wiederholt. Die Sprache enthält beispielsweise $\varepsilon$, ab, aabb und aaabbb.
Wortproblem
Beim Wortproblem prüfst du für eine vorgegebene Grammatik $G$ und ein Wort $w$, ob $w\in L(G)$ gilt.
Für kleine Grammatiken kannst du dazu eine vollständige Ableitung suchen. Ein abgebrochener Versuch beweist jedoch noch nicht, dass das Wort unmöglich ist: Vielleicht gibt es einen anderen Ableitungsweg.
Eine erfolgreiche Ableitung beweist die Zugehörigkeit. Für die Nichtzugehörigkeit musst du begründen, warum kein möglicher Ableitungsweg zum Wort führen kann.
Wie speichert eine Grammatik einfache Zustände?
Nichtterminale können festhalten, in welcher Phase sich die Wortbildung befindet. Dadurch lassen sich Bedingungen ausdrücken, die eine einzelne Regel nicht zuverlässig überwachen könnte.
Gesucht sind alle Wörter, die mit mindestens einer 0 beginnen und danach eine gerade Anzahl von 1 enthalten. Eine passende rechtslineare Grammatik verwendet
$$N=\{S,B,C\},\qquad T=\{0,1\}$$
und die Regeln
$$S\to0S\mid0B$$
$$B\to\varepsilon\mid1C$$
$$C\to1B$$
Die Nichtterminale haben klare Aufgaben:
- $S$ erzeugt mindestens eine
0und bleibt im Nullabschnitt. - $B$ steht für eine gerade Anzahl bisher erzeugter
1. Nur hier darf die Ableitung enden. - $C$ steht für eine ungerade Anzahl erzeugter
1. Von hier muss noch eine zweite1folgen.
Das Wort 0011 wird so erzeugt:
$$S\Rightarrow0S\Rightarrow00B\Rightarrow001C\Rightarrow0011B\Rightarrow0011$$
Nach der ersten 1 befindet sich die Ableitung in $C$ und darf nicht enden. Erst die zweite 1 führt zurück nach $B$. Dort beendet $B\to\varepsilon$ die Ableitung.
001 kann nicht entstehen: Nach der einzigen 1 steht das nicht beendbare $C$. Dagegen entsteht 0 durch $S\Rightarrow0B\Rightarrow0$.
Wie werden Grammatiken eingeordnet?
Die Chomsky-Hierarchie ordnet Grammatiken nach den Einschränkungen ihrer Produktionen. Je stärker die Regeln eingeschränkt sind, desto spezieller ist die erzeugbare Sprachklasse.
| Typ | Name | Kennidee |
|---|---|---|
| 3 | regulär | Höchstens ein Nichtterminal steht rechts in einer festen Randposition. |
| 2 | kontextfrei | Links steht genau ein Nichtterminal, etwa $A\to\alpha$. |
| 1 | kontextsensitiv | Eine Ersetzung kann vom umgebenden Kontext abhängen. |
| 0 | allgemein | Für Produktionen gelten keine zusätzlichen Einschränkungen der engeren Typen. |
Für die Sprachklassen gilt die echte Inklusionskette
$$L_3\subset L_2\subset L_1\subset L_0$$
Jede reguläre Sprache ist somit auch kontextfrei, aber nicht jede kontextfreie Sprache ist regulär.
Bei einer rechtslinearen Typ-3-Regel steht das optionale Nichtterminal rechts, zum Beispiel $A\to aB$. Bei einer linkslinearen Regel steht es links, zum Beispiel $A\to Ba$. Beide Formen beschreiben die Klasse der regulären Sprachen.
Reguläre Grammatiken und endliche Automaten sind gleich mächtig: Nichtterminale entsprechen Zuständen, und eine Regel $q\to aq'$ entspricht einem Übergang mit dem Zeichen $a$ von $q$ nach $q'$. Eine Regel $q\to\varepsilon$ kennzeichnet bei der üblichen Umwandlung einen akzeptierenden Zustand.
Unterscheide die Klasse einer konkreten Grammatik von der Klasse ihrer Sprache. Eine Grammatik wird nach der Form ihrer tatsächlichen Regeln eingeordnet. Eine Sprache gehört zu einer Klasse, wenn es irgendeine passende Grammatik dieser Klasse gibt. Verschiedene Grammatiken können dieselbe Sprache erzeugen.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Formale Grammatik
- Bestandteile: Nichtterminale, Terminale, Produktionen und Startsymbol
- Ableitung: Regeln schrittweise anwenden
- Fertiges Wort: enthält ausschließlich Terminale
- Sprache: Menge aller ableitbaren Terminalwörter
- Wortproblem: Zugehörigkeit eines Wortes prüfen
- Zustände: Nichtterminale speichern strukturelle Information
- Hierarchie: Typ 3 ist in Typ 2, Typ 2 in Typ 1 und Typ 1 in Typ 0 enthalten
Abschluss-Check
Wenn du alle drei Aufgaben begründen kannst, beherrschst du den Kern: Du liest die Bestandteile einer Grammatik, verfolgst ihre Ableitungen und erkennst, welche Wörter ihre Regeln tatsächlich erzeugen.