Chomsky-Hierarchie

Der amerikanische Linguist N. Chomsky hat die Sprachklassen in eine Hierarchie eingereiht:

 Hierbei bedeuten

• $\mathcal L_3 \quad$ die Klasse der regulären Sprachen

• $\mathcal L_2 \quad$ die Klasse der kontextfreien Sprachen

• $\mathcal L_1 \quad$ die Klasse der kontextsensitiven Sprachen

• $\mathcal L_0 \quad$ die Klasse der rekursiv aufzählbaren Sprachen

Die Chomsky-Hierarchie besagt, dass die Sprachklassen von $\mathcal L_3$ bis $\mathcal L_0$ echt ineinander enthalten sind.

Das bedeutet beispielsweise, dass jede reguläre Sprache gleichzeitig auch eine kontextfreie Sprache ist. Eine kontextfreie Sprache muss jedoch keine reguläre Sprache sein.

Die Sprachklassen lassen sich charakterisieren durch bestimmte

• Grammatiktypen

• Automatentypen

So wird beispielsweise die Klasse $\mathcal L_2$ der kontextfreien Sprachen durch kontextfreie Grammatiken erzeugt und durch nichtdeterministische Stackautomaten erkannt.

In derselben Weise sind die anderen Sprachklassen durch bestimmte Grammatiktypen und durch bestimmte Automatentypen charakterisiert.

Mithilfe von entsprechenden Konstruktionsverfahren kannst du die Grammatiktypen in zugehörige Automatentypen überführen und umgekehrt.

Übersicht

Anhand der folgenden Tabelle ersiehst du, welche Grammatiktypen die jeweiligen Sprachen erzeugen und welche Automatentypen (in der nichtdeterministischen Version) die jeweiligen Sprachen erkennen.

Sowohl die Grammatiktypen als auch die Automatentypen, die den Sprachklassen entsprechen, sind von $\mathcal L_3$ bis $\mathcal L_0$ jeweils Spezialfälle voneinander. Somit ergibt sich zunächst die Inklusion $\subseteq$.

Grammatiktypen

Noch einmal zur Erinnerung: Eine Grammatik ist ein Tupel $G =(V, T, P, S)$; hierbei sind

• $V$ das Alphabet der Nichtterminalzeichen

• $T$ das Alphabet der Terminalzeichen, $A = V \cup T$ ist das Gesamtalphabet

• $P\subseteq A^+\times A^*$ die Menge der Produktionen

• $S$ das Startsymbol

Allgemeine Grammatik

Der allgemeinste Grammatiktyp enthält keine Beschränkungen für die Art der Produktionen. Jede Produktion hat die Form

mit $u \in A^+,~ v \in A^*$.

Eine Sprache gehört zur Sprachklasse $\mathcal L_0$, wenn sie von einer Grammatik dieser Form erzeugt wird.

Expansive Grammatik

Ein speziellerer Grammatiktyp ist die expansive Grammatik; hier hat jede Produktion die Form

mit $u \in A^+,~ v \in A^+ ~$ und

Die erzeugten Wörter in jeder Ableitungsfolge, beginnend beim Startsymbol $S$, werden also immer länger oder bleiben gleich lang, sie werden jedenfalls nie kürzer – daher die Bezeichnung expansive Grammatik.

Eine Sprache gehört zur Sprachklasse $\mathcal L_1$, wenn sie von einer Grammatik dieser Form erzeugt wird.

Kontextfreie Grammatik

Ein noch speziellerer Grammatiktyp ist die kontextfreie Grammatik; hier hat jede Produktion die Form

mit $u \in V,~ v \in A^+$.

Auf der linken Seite jeder Produktion steht also immer nur ein einziges Nichtterminalzeichen, auf der rechten Seite steht ein beliebiges nichtleeres Wort.

Offenbar ist eine kontextfreie Grammatik ein Spezialfall einer expansiven Grammatik.

Eine Sprache gehört zur Sprachklasse $\mathcal L_2$, wenn sie von einer Grammatik dieser Form erzeugt wird.

Rechtslineare Grammatik

Der speziellste Grammatiktyp ist die rechtslineare Grammatik; hier hat jede Produktion die Form

mit

$X,Y \in V,~ a \in T$.

Offenbar ist eine rechtslineare Grammatik ein Spezialfall einer kontextfreien Grammatik.

Eine Sprache gehört zur Sprachklasse $\mathcal L_3$, wenn sie von einer Grammatik dieser Form erzeugt wird.

Erzeugung des leeren Worts $\varepsilon$

Mit den Grammatiken vom Typ 1, 2 und 3 ist es nicht möglich, das leere Wort $\varepsilon$ zu erzeugen – eine eigentlich unnötige Einschränkung. Deshalb wird bei diesen Grammatiken als einzige Ausnahme ist die Produktion

erlaubt, um gegebenenfalls das leere Wort zu erzeugen. Dann aber darf $S$ nicht auf der rechten Seite einer Produktion vorkommen. Durch Einführung eines neuen Nichtterminalzeichens $S'$ und durch geeignete Umbenennungen lässt sich jede Grammatik so umformen.

Meistens wird bei der Definition einer kontextfreien Grammatik in allen Produktionen das leere Wort $\varepsilon$ auf der rechten Seite erlaubt. Es ist aber dann möglich, eine solche Grammatik in die oben erwähnte strengere Form umzuformen

Automatentypen

Auch die entsprechenden Automatentypen der Chomsky-Hierarchie sind jeweils Spezialfälle voneinander.

Du erkennst dies an folgender Überlegung: Ein Automat kann einen spezielleren Automaten simulieren. Er kann alles, was der speziellere Automat kann.

• Ein Stackautomat kann einen endlichen Automaten simulieren, indem er seinen Stack nicht benutzt.

• Eine linear beschränkte Turingmaschine kann einen Stackautomaten simulieren. Sie liest das Eingabewort von links nach rechts und benutzt den Teil des Arbeitsbandes, dessen Eingabezeichen sie schon gelesen hat, als Stack. Allerdings ist hierfür der Stackautomat etwas strenger zu definieren, in der Weise, dass er nur dann ein Zeichen in den Stack schreibt, wenn er ein Eingabezeichen gelesen hat. Dies stellt aber keine wesentliche Einschränkung dar.

• Und eine Turingmaschine kann natürlich eine linear beschränkte Turingmaschine simulieren, indem sie nur den Teil des Arbeitsbandes benutzt, auf dem das Eingabewort steht.

Echte Inklusion

Die bisherigen Überlegungen besagen nur, dass die Sprachklassen der Chomsky-Hierarchie ineinander enthalten sind oder auch gleich sind.

Um die echte Inklusion $\subset$ zu zeigen, gibst du Sprachen an, die in der einen Sprachklasse enthalten sind, aber nicht in der vorhergehenden.

Die Sprache $L = \{a^nb^n ~|~ n \in \mathbb N\}$ ist kontextfrei, aber nicht regulär. Damit gilt $\mathcal L_2 \not = \mathcal L_3$.

Die Sprache $L = \{a^nb^nc^n ~|~ n \in \mathbb N\}$ ist expansiv, aber nicht kontextfrei. Damit gilt $\mathcal L_1 \not= \mathcal L_2$.

Etwas schwieriger zu zeigen ist die echte Inklusion von $\mathcal L_1$ in $\mathcal L_0$. So gibt es beispielsweise Sprachen, die rekursiv aufzählbar sind, aber deren Komplement nicht rekursiv aufzählbar ist. Eine solche Sprache wird als nicht entscheidbar bezeichnet. Jede expansive Sprache ist aber entscheidbar. Damit gilt $\mathcal L_0 \not= \mathcal L_1$.