Chomsky-Hierarchie

Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken die formale Sprachen erzeugen. Sie wurde 1956 von Noam Chomsky beschrieben.

Eine formale Grammatik besteht aus Terminal-Symbolen, Nichtterminal-Symbolen (darunter das Startsymbol) und Produktions-Regeln.
Die Grammatik definiert dann eine formale Sprache, die aus allen Wörtern besteht, die nur aus Terminal-Symbolen bestehen und vom Startsymbol abgeleitet werden können.

Die Hierarchie

Die Chomsky-Hierarchie besteht aus folgenden Ebenen:

• Typ-0-Grammatiken (auch unbeschränkte Grammatiken genannt) sind alle wie oben definierbaren Grammatiken. Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turing-Maschine erkannt werden kann und für jede Sprache die von einer Turing-Maschine erkannte werden kann existiert eine Typ-0-Grammatik, die diese Sprache erzeugt. Eine Sprache, die von einer Turing-Maschine erkannt werden kann ist dabei definiert als eine Sprache, zu der eine Turing-Maschine existiert, die genau bei den Wörtern hält, die zur Sprache gehören. Diese Sprachen sind auch bekannt, als die rekursiv aufzählbaren Sprachen (oft auch semientscheidbare Sprachen genannt). Man beachte, dass sich diese Menge von Sprachen von der Menge der der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet.

• Typ-1-Grammatiken (auch kontextsensitive Grammatiken genannt) erzeugen genau die kontextsensitiven Sprachen, d.h. jede Typ-1-Grammatik erzeugt eine kontextsenstive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt. Typ-1-Grammatiken besitzen nur Regeln der Form $\alpha A\beta \rightarrow \alpha \gamma \beta$, wobei $A$ ein Nichtterminal und $\alpha ,\beta ,\gamma$ Wörter bestehend aus Terminalen und Nichtterminalen sind. Die Wörter $\alpha$ und $\beta$ können leer sein, aber $\gamma$ muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten. Die einzige Ausnahme ist, dass die Grammatik die Regel $S\rightarrow \epsilon$ enthalten darf, wobei $S$ das Startsymbol und $\epsilon$ (wie oben erläutert) das leere Wort ist. Diese Regel wird eventuell benötigt, um das leere Wort $\epsilon$ ableiten zu können. Die kontextsensitiven Sprachen sind genau die Sprachen, die von einem nichtdeterministischen LBA erkannt werden können, d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl $a$ so dass das Band der Turing-Maschine höchstens $a\cdot x$ Felder besitzt, wobei $x$ die Länge des Eingabewortes ist).

• Typ-2-Grammatiken (auch kontextfreie Grammatiken genannt) erzeugen genau die kontextfreien Sprachen, d.h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt. Typ-2-Grammatiken besitzen nur Regeln der Form $A\rightarrow \gamma$, wobei $A$ ein Nichtterminal und $\gamma$ ein Wort bestehend aus Terminalen und Nichtterminalen ist. Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen.

• Typ-3-Grammatiken (auch reguläre Grammatiken genannt) erzeugen genau die regulären Sprachen, d.h. jede Typ-3-Grammatik erzeugt eine reguläre Sprache und zu jeder regulären Sprache existiert eine Typ-3-Grammatik, die diese erzeugt. Typ-3-Grammatiken besitzen nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Termial, eventuell gefolgt von einem Nichtterminal bestehen. Aus dem selben Grund wie bei Typ-1-Grammtiken ist auch hier die Regel $S\rightarrow \epsilon$ als Ausnahme erlaubt, allerdings nur, wenn $S$ nicht auf der rechten Seite einer Regel erscheint. Reguläre Sprachen können alternativ auch durch reguläre Ausdrücke beschrieben werden und die regulären Sprachen sind genau die Sprachen, die von endlichen Automaten erkannt werden können. Sie werden gewöhnlich genutzt, um Suchmuster oder die lexikalische Struktur von Programmiersprachen zu definieren. Eine weitere Anwendung existiert in der Morphologie.

Jede reguläre Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv und jede kontextsensitive Sprache ist rekursiv aufzählbar.
Dabei handelt es sich um echte Teilmengenbeziehungen, d.h. es gibt rekursive aufzählbare Sprachen, die nicht kontextsensitiv sind, kontextsensitive Sprachen, die nicht kontextfrei sind und kontextfreie Sprachen, die nicht regulär sind.

Die folgende Tabelle fasst die vier Grammatiktypen, die Form ihrer Regeln, die Sprachen die sie erzeugen und die Automatentypen die sie erkennen zusammen.

Grammatik	Regeln	Sprachen	Automaten
Typ-0	keine Einschränkungen	rekursiv aufzählbar	Turing-Maschine
Typ-1	$\alpha A\beta \rightarrow \alpha \gamma \beta$	kontextsensitiv	linear platzbeschränkte nichtdeterministische Turing-Machine
Typ-2	$A\rightarrow \gamma$	kontextfrei	nichtdeterministischer Kellerautomat
Typ-3	$A\rightarrow aB$ $A\rightarrow a$	regulär	endlicher Automat

Literatur

• Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
• Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112