Chomsky-Hierarchie: Grammatiktypen verstehen

Eine formale Grammatik hat Regeln, mit denen man Wörter erzeugt. Man startet beim Startsymbol und ersetzt Symbole nach den Regeln. Ein Ergebnis gilt nur dann als Wort der Sprache, wenn es keine Nichtterminalsymbole mehr enthält.

Die Chomsky-Hierarchie umfasst vier Typen von Grammatiken, gezählt von 0 bis 3. Die Typen unterscheiden sich darin, wie streng die Regeln eingeschränkt sind. Typ 0 hat keine Einschränkung an die Gestalt der Regeln. Es muss nur links in jeder Regel wenigstens ein Nichtterminalsymbol stehen. Typ 1 bis Typ 3 sind dann zunehmend stärker eingeschränkt.

Typ 1 heißt kontextsensitiv. Nach der Definition αAβ → αγβ haben die Regeln diese Form (oder S → ε). Dabei ist A ein Nichtterminal. α, β und γ sind Wörter aus Terminalen und Nichtterminalen. α und β können leer sein, γ muss aber mindestens ein Symbol enthalten. Die Regel S → ε erlaubt man nur als Ausnahme, wenn das Startsymbol S nirgends auf einer rechten Seite vorkommt.

Typ 2 heißt kontextfrei. In Chomskys ursprünglicher Definition steht links in jeder Regel genau ein Nichtterminalsymbol und rechts eine beliebige nichtleere Folge von Symbolen.

Typ 3 heißt regulär. In Chomskys ursprünglicher Definition (ohne ε auf rechten Seiten) steht rechts genau ein Terminalsymbol und höchstens ein weiteres Nichtterminalsymbol. Dieses Nichtterminal steht in allen Regeln entweder immer vor oder immer hinter dem Terminal. Kommen beide Stellungen in einer Grammatik vor, ist sie nicht regulär.

Nach der Definition ist eine Grammatik vom Typ 3 auch vom Typ 2, eine vom Typ 2 auch vom Typ 1 und eine vom Typ 1 auch vom Typ 0. Die Umkehrungen gelten nicht. Chomsky verlangte für Typ 1, 2 und 3, dass die rechte Seite nicht kürzer als die linke ist. Heute lässt man oft das leere Wort auf rechten Seiten zu. Hier bleiben wir bei der strengen Form.

Jeder Grammatiktyp erzeugt genau eine Sprachklasse. Zu jeder Klasse gehört ein Automatenmodell, das genau diese Sprachen erkennt. Wie die Automaten arbeiten, lernst du hier nicht. Du ordnest sie nur zu.

Typ 0 erzeugt genau die Sprachen, die eine Turingmaschine akzeptieren kann. Diese Sprachen heißen rekursiv aufzählbar. Typ 1 erzeugt die kontextsensitiven Sprachen. Sie erkennt genau eine nichtdeterministische, linear beschränkte Turingmaschine. Ihr Band hat höchstens a · x Felder, für eine feste Zahl a und die Länge x der Eingabe.

Typ 2 erzeugt die kontextfreien Sprachen. Sie erkennt genau ein nichtdeterministischer Kellerautomat. Eine Teilmenge der kontextfreien Sprachen bildet die theoretische Basis für die Syntax der meisten Programmiersprachen. Typ 3 erzeugt die regulären Sprachen. Sie erkennt genau ein endlicher Automat. Man kann sie auch durch reguläre Ausdrücke beschreiben.

Als Kurzschreibweise für die Klassen gilt REG ⊂ CF ⊂ CS ⊂ RE. Das sind die regulären, kontextfreien, kontextsensitiven und rekursiv aufzählbaren Sprachen. Sprachen eines eingeschränkteren Grammatiktyps sind üblicherweise einfacher algorithmisch zu verarbeiten, aber weniger ausdrucksmächtig.

Eine Grammatik besteht aus Regeln. Eine Sprache ist eine Menge von Wörtern. Der Typ einer Grammatik hängt von der Form ihrer Regeln ab. Der Typ einer Sprache hängt davon ab, ob es eine passende Grammatik gibt: Eine Sprache ist vom Typ i, wenn es eine Typ-i-Grammatik gibt, die sie erzeugt. Eine solche Grammatik genügt. Es gibt also zwei Hierarchien nebeneinander, eine der Grammatiken und eine der Sprachen.

Deshalb kann eine Grammatik nicht vom Typ i sein, während ihre Sprache trotzdem vom Typ i ist. Dafür muss nur eine andere Grammatik vom Typ i dieselbe Sprache erzeugen. Aus „die Grammatik ist nicht vom Typ i“ folgt also nicht „die Sprache ist nicht vom Typ i“.

Ein Fall: Einige Autoren nennen eine Grammatik schon kontextsensitiv, wenn bis auf S → ε alle Regeln w1 → w2 die Bedingung |w1| ≤ |w2| erfüllen. Häufiger heißt sie monoton oder nichtverkürzend. Monotone Grammatiken erzeugen genau die kontextsensitiven Sprachen. Nicht jede monotone Grammatik ist aber nach der Definition αAβ → αγβ vom Typ 1. Ihre Sprache ist trotzdem vom Typ 1.

Zwischen den Sprachklassen benachbarter Ebenen besteht eine echte Teilmengenbeziehung. Jede reguläre Sprache ist kontextfrei, aber nicht jede kontextfreie Sprache ist regulär. Die Sprache {aⁿbⁿ | n ≥ 1} ist vom Typ 2, aber nicht vom Typ 3. Die Sprache {aⁿbⁿcⁿ | n ≥ 1} ist vom Typ 1, aber nicht vom Typ 2. Solche Beweise führt man oft mit dem Schleifensatz (Pumping-Lemma). Hier nennen wir nur die Ergebnisse.

Linksreguläre und rechtsreguläre Grammatiken erzeugen genau dieselbe Sprachklasse. Grammatiken, die beide Arten mischen, sind nicht regulär. Als Klasse erzeugen sie eine echt größere Sprachklasse.