Chomsky-Hierarchie
Die Chomsky-Hierarchie ordnet Grammatiken nach der Form ihrer Regeln. Daran lässt sich ablesen, welcher Automat eine Sprache erkennen kann.
Definition
Die Chomsky-Hierarchie teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 bis Typ 3. Je höher die Nummer, desto strenger sind die Regeln. Eine Sprache wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.
Die Sprachklassen sind ineinander enthalten. Jede Sprache vom Typ 3 lässt sich auch mit einer Grammatik vom Typ 2 erzeugen, jede Sprache vom Typ 2 auch mit einer vom Typ 1 und jede Sprache vom Typ 1 auch mit einer vom Typ 0. Die Umkehrungen gelten nicht.
- [math]\displaystyle{ \text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0} }[/math]
Sprachklassen und Automatenmodelle

Die Tabelle nennt zu jedem Typ die Sprachklasse, die erlaubte Regelform und den Automaten, der genau diese Sprachen erkennt. Dabei sind [math]\displaystyle{ A }[/math] und [math]\displaystyle{ B }[/math] Nichtterminale, [math]\displaystyle{ a }[/math] ist ein Terminal und [math]\displaystyle{ \beta }[/math] ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen.
| Typ | Sprachklasse | Regelform | Automatenmodell |
|---|---|---|---|
| 0 | rekursiv aufzählbar | beliebig, links mindestens ein Nichtterminal | Turingmaschine |
| 1 | kontextsensitiv | rechte Seite mindestens so lang wie die linke, Ausnahme [math]\displaystyle{ S \to \varepsilon }[/math] | linear beschränkter Automat |
| 2 | kontextfrei | [math]\displaystyle{ A \to \beta }[/math] | Kellerautomat |
| 3 | regulär | [math]\displaystyle{ A \to aB }[/math], [math]\displaystyle{ A \to a }[/math], Ausnahme [math]\displaystyle{ S \to \varepsilon }[/math] | endlicher Automat |
Für alle kontextfreien Sprachen braucht es nichtdeterministische Kellerautomaten, denn deterministische erkennen nur einen Teil von ihnen.
Beispiele
Sprachen einordnen
Jede Sprache wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.
- Die Wörter des Kaffeeautomaten bilden die endliche Sprache [math]\displaystyle{ L = \{KKKK, EE, EKK, KEK, KKE\} }[/math]. Ein endlicher Automat erkennt sie, und eine Grammatik mit nur den Regelformen [math]\displaystyle{ A \to aB }[/math] und [math]\displaystyle{ A \to a }[/math] erzeugt sie, siehe Reguläre Grammatik. Die Sprache ist regulär: Typ 3.
- Korrekt geklammerte Ausdrücke erzeugt die Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]. Ihre Regeln haben links genau ein Nichtterminal, die Sprache ist also kontextfrei, siehe Kontextfreie Grammatik. Ein endlicher Automat kann beliebig tiefe Klammerung nicht mitzählen, die Sprache ist deshalb nicht regulär, siehe Grenzen regulärer Sprachen. Sie gehört zu Typ 2, nicht zu Typ 3.
- Die Sprache [math]\displaystyle{ \{a^n b^n c^n \mid n \geq 1\} }[/math] verlangt gleich viele a, b und c in dieser Reihenfolge. Sie ist kontextsensitiv, aber nicht kontextfrei: Typ 1, nicht Typ 2. Der Beweis bleibt hier aus. Anschaulich gesagt kann ein Keller zwei Anzahlen vergleichen, aber nicht drei.