Chomsky-Hierarchie

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

Formale Grammatiken

Eine formale Grammatik besteht aus einer endlichen Menge von Terminal-Symbolen (im folgenden kurz Terminale genannt), einer endlichen Menge von Nichtterminal-Symbolen (im folgenden kurz Nichtterminale genannt), einer endlichen Menge von Produktions-Regeln (im folgenden kurz Regeln genannt) und einem Startsymbol, welches zu den Nichtterminalen gehört.

Eine Regel besteht aus einer linken und einer rechten Seite, die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Eine Regel kann auf ein Wort aus Terminalen und Nichtterminalen angewendet werden, wobei ein beliebigen Vorkommens der linken Seite der Regel im Wort durch die rechten Seite der Regel ersetzt wird. Eine Ableitung ist dann eine Folge von solchen Anwendungen der Regeln. Die Grammatik definiert dann eine formale Sprache, die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol abgeleitet werden können.

Nichtterminale werdem gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert. Das Startsymbol wird meistens durch das $S$ repräsentiert.

Beispiel

Wir betrachten die Grammatik mit den Terminalen $\{a,b\}$, den Nichtterminalen $\{S,A,B\}$ und den Regeln

$S\rightarrow ABS$

$S\rightarrow \epsilon$ (with $\epsilon$; the empty string)

$BA\rightarrow AB$

$BS\rightarrow b$

$Bb\rightarrow bb$

$Ab\rightarrow ab$

$Aa\rightarrow aa$

und dem Startsymbol $S$, definiert die Sprache aller Wörter der Form $a^{n}b^{n}$, d.h. $n$ Kopien von $a$ gefolgt von $n$ Kopien von $b$.

Die Hierarchie

Die Chomsky-Hierarchie besteht nun aus folgenden Leveln:

• 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$ das leere Wort ist, also das Wort, welches keine Symbole enthält. 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ären 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.

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

Die folgende Tabelle fasst die vier Grammtiktypen, 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$ </math>A \rightarrow a</math>	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