Mit Google fortfahren
Chomsky-Hierarchie: Grammatiktypen verstehen
Die Chomsky-Hierarchie ordnet formale Grammatiken nach ihren Produktionsregeln. Typ 0 erlaubt am meisten, Typ 3 ist am stärksten eingeschränkt. Je stärker die Regeln eingeschränkt sind, desto kleiner ist die zugehörige Sprachklasse.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie erzeugt eine Grammatik Wörter?
Eine formale Grammatik beschreibt mit endlich vielen Regeln möglicherweise unendlich viele Wörter.
Formale Grammatik
Eine Grammatik ist ein Vier-Tupel $G=(V,\Sigma,P,S)$:
- $V$ ist die Menge der Nichtterminale. Diese Symbole können ersetzt werden.
- $\Sigma$ ist das Alphabet der Terminale. Aus ihnen bestehen die fertigen Wörter.
- $P$ ist die Menge der Produktionsregeln.
- $S$ ist das Startsymbol.
Eine Regel wie $S\to aS$ ersetzt ein vorkommendes $S$ durch $aS$. Ein Wort gehört erst dann zur erzeugten Sprache, wenn nur noch Terminale vorkommen.
Die Grammatik mit den Regeln
$$S\to aS\mid b$$
erzeugt Wörter der Form $a^n b$ für $n\geq 0$.
Für $aab$ lautet eine vollständige Ableitung:
$$S\Rightarrow aS\Rightarrow aaS\Rightarrow aab$$
Die Folge $aaS$ ist noch kein Wort der Sprache, weil sie das Nichtterminal $S$ enthält.
Woran erkennst du die vier Typen?
Für die folgende Übersicht verwenden wir eine strenge, gut vergleichbare Konvention. Dabei ist die linke Regelseite nicht leer und enthält mindestens ein Nichtterminal.
Typ 0: unbeschränkt
Bei Typ 0 gibt es keine zusätzliche Einschränkung der Regelform. Eine Regel darf eine Satzform auch verkürzen.
Typ-0-Grammatiken erzeugen die rekursiv aufzählbaren Sprachen. Das passende Modell ist die Turingmaschine.
Typ 1: nichtverkürzend oder kontextsensitiv
Für jede Regel $u\to v$ gilt:
$$|u|\leq |v|$$
Die rechte Seite ist also mindestens so lang wie die linke. Solche Regeln heißen nichtverkürzend, monoton oder expansiv.
Eine syntaktisch kontextsensitive Regel hat genauer die Form
$$\alpha A\beta\to\alpha\gamma\beta$$
Dabei wird $A$ nur in der Umgebung $\alpha\_\beta$ ersetzt. Nichtverkürzende und syntaktisch kontextsensitive Grammatiken erzeugen dieselbe Sprachklasse, obwohl ihre einzelnen Regelformen nicht identisch sein müssen.
Typ 1 entspricht den kontextsensitiven Sprachen und linear beschränkten Turingmaschinen.
Typ 2: kontextfrei
Links steht genau ein Nichtterminal:
$$A\to w$$
In der strengen Form ist $w$ nicht leer. Weil nur $A$ ersetzt wird, hängt die Regelanwendung nicht von seinen Nachbarsymbolen ab.
Typ 2 entspricht den kontextfreien Sprachen und den nichtdeterministischen Kellerautomaten.
Typ 3: regulär
Eine rechtsreguläre Grammatik verwendet Regeln der Form
$$A\to aB\quad\text{oder}\quad A\to a$$
Dabei sind $A$ und $B$ Nichtterminale und $a$ ist ein Terminal. Linksreguläre Grammatiken setzen das optionale Nichtterminal entsprechend vor das Terminal. Innerhalb einer regulären Grammatik wird die Orientierung nicht gemischt.
Typ 3 entspricht den regulären Sprachen und den endlichen Automaten.
Beim leeren Wort $\varepsilon$ gibt es verschiedene Konventionen. Häufig wird $S\to\varepsilon$ als Ausnahme zugelassen, wenn das Startsymbol $S$ auf keiner rechten Regelseite vorkommt. Manche Definitionen erlauben weitere $\varepsilon$-Regeln oder terminale Zeichenketten in regulären Regeln. Die erzeugten Sprachklassen bleiben bei geeigneten Umformungen gleich. Bei einer konkreten Aufgabe musst du deshalb zuerst die verwendete Konvention prüfen.
Von Typ 0 zu Typ 3 werden die Regeln strenger: beliebig – nichtverkürzend – ein Nichtterminal links – linear.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Bei Typ 2 steht links genau . Bei Typ 1 darf eine gewöhnliche Regel die Satzform . Typ 3 gehört zu den Grammatiken.
Wie liest du die Hierarchie?
Die Sprachklassen sind echt ineinander enthalten:
$$L_3\subsetneq L_2\subsetneq L_1\subsetneq L_0$$
Das bedeutet zum Beispiel:
- Jede reguläre Sprache ist auch kontextfrei.
- Es gibt kontextfreie Sprachen, die nicht regulär sind.
- Jede kontextfreie Sprache ist auch kontextsensitiv.
- Typ 0 umfasst alle drei stärker eingeschränkten Klassen.
Eine Sprache wie
$$\{a^n b^n\mid n\geq 1\}$$
ist kontextfrei, aber nicht regulär. Ein endlicher Automat besitzt nur endlich viele Zustände und kann deshalb nicht beliebig große Anzahlen von $a$ speichern, um sie später mit der Anzahl der $b$ zu vergleichen. Diese anschauliche Begründung erklärt die Modellgrenze; ein formaler Nicht-Regularitätsbeweis benötigt ein eigenes Beweisverfahren.
Die Sprache
$$\{a^n b^n c^n\mid n\geq 1\}$$
ist kontextsensitiv, aber nicht kontextfrei. Hier müssen sogar drei beliebig große Anzahlen übereinstimmen.
Wie ordnest du Regeln und Grammatiken ein?
Prüfe eine Grammatik von der stärksten Einschränkung aus:
- Steht links genau ein Nichtterminal?
- Ist die rechte Seite durchgehend links- oder rechtslinear? Dann ist die Grammatik Typ 3.
- Ist sie nicht linear, steht links aber immer genau ein Nichtterminal? Dann ist sie Typ 2.
- Gibt es mehrsymbolige linke Seiten, aber keine verkürzende Regel? Dann kommt Typ 1 infrage.
- Verletzt mindestens eine Regel die höheren Bedingungen, bleibt Typ 0.
Betrachte drei Regeln getrennt:
- $A\to aB$ erfüllt die rechtsreguläre Form und ist als Regel mit Typ 3 vereinbar.
- $A\to aAb$ besitzt genau ein Nichtterminal links, ist aber nicht linear. Sie ist mit Typ 2 vereinbar.
- $AB\to A$ verkürzt von zwei Symbolen auf eines. Nach der strengen Konvention ist sie nur mit Typ 0 vereinbar.
Für den Typ einer ganzen Grammatik müssen alle Regeln die jeweilige Bedingung erfüllen.
Grammatiktyp und Sprachtyp
Der Typ einer Grammatik hängt von ihren konkreten Regeln ab. Der Typ einer Sprache hängt davon ab, ob irgendeine Grammatik des betreffenden Typs diese Sprache erzeugt.
Aus einer ungeschickt formulierten Typ-2-Grammatik folgt daher nicht automatisch, dass ihre Sprache nicht regulär ist. Vielleicht gibt es für dieselbe Sprache noch eine Typ-3-Grammatik.
Welche Automaten passen zu den Typen?
Grammatiken erzeugen Wörter; Automaten erkennen Wörter. Für jede Stufe gehören Grammatikklasse, Sprachklasse und Automatenmodell zusammen.
| Typ | Sprachklasse | Automatenmodell |
|---|---|---|
| 0 | rekursiv aufzählbar | Turingmaschine |
| 1 | kontextsensitiv | linear beschränkte Turingmaschine |
| 2 | kontextfrei | nichtdeterministischer Kellerautomat |
| 3 | regulär | endlicher Automat |
Ein Kellerautomat erweitert den endlichen Automaten um einen Stapelspeicher. Damit kann er beispielsweise die gelesenen $a$ zählen und beim Lesen der $b$ wieder abbauen. Eine linear beschränkte Turingmaschine besitzt mehr Arbeitsmöglichkeiten, darf aber nur einen durch die Eingabelänge beschränkten Bandbereich nutzen.
Bei einer Typ-0-Sprache akzeptiert eine passende Turingmaschine jedes enthaltene Wort. Für ein nicht enthaltenes Wort muss sie jedoch nicht anhalten. Erkennen ist daher schwächer als Entscheiden, bei dem die Maschine für jede Eingabe anhält.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Chomsky-Hierarchie
- Typ 0: unbeschränkt und Turingmaschine
- Typ 1: nichtverkürzend und linear beschränkte Turingmaschine
- Typ 2: kontextfrei und Kellerautomat
- Typ 3: regulär und endlicher Automat
- Regelbeschränkung: von Typ 0 zu Typ 3 zunehmend
- Sprachklassen: echte Teilmengen
- Einordnung: Grammatiktyp und Sprachtyp getrennt prüfen
Abschluss-Check
Du kannst die Hierarchie sicher anwenden, wenn du zuerst die Regeln einer Grammatik prüfst, anschließend Grammatik- und Sprachtyp unterscheidest und zuletzt das passende Automatenmodell zuordnest.