Chomsky-Hierarchie

Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen. Sie wurde 1956 von Noam Chomsky beschrieben. Die vier von Chomsky beschriebenen Grammatiktypen entstehen dabei ausgehend von einer nicht eingeschränkten Grundgrammatik (der Typ-0-Grammatik) dergestalt, dass zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden. Eine Typ-1-Grammatik ist also ein Spezialfall (eine Echte Teilmenge) einer Typ-0-Grammatik, eine Typ-2-Grammatik ein Spezialfall einer Typ-1-Grammatik usw.

Entsprechend dem Typ einer Grammatik, die mindestens erforderlich ist, um eine bestimmte formale Sprache zu erzeugen, werden auch formale Sprachen in dieselben Kategorien von Typ 3 bis Typ 0 eingeteilt.

Sei im Folgenden die formale Grammatik $G=\left(N,\Sigma ,P,S\right)$ angenommen. $N$ stellt die Menge der Nichtterminalsymbole, $\Sigma$ die Menge der Terminalsymbole, $P$ die Menge von Regeln und $S$ das Startsymbol dar (Einzelheiten siehe unter formale Grammatik).

Die Hierarchie

Typ-0-Grammatik (allgemeine Chomsky-Grammatik)

Typ-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. Es handelt sich dabei um alle definierbaren Grammatiken.

Man schreibt $G\in {\mbox{Typ}}_{0}$.

Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turing-Maschine akzeptiert werden kann und umgekehrt existiert für jede Sprache, die von einer Turingmaschine akzeptiert werden kann, eine Typ-0-Grammatik, die diese Sprache erzeugt. 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 rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet, welche durch Turing-Maschinen erkannt werden können, d. h. die zugehörige Turingmaschine hält bei jedem Wort und liefert als Ergebnis 0 (Wort gehört nicht zur Sprache) oder 1 (Wort gehört zur Sprache).

Typ-1-Grammatik (kontextsensitive Grammatik)

Typ-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. Es handelt sich dabei um Typ-0-Grammatiken mit $\forall (w_{1}\rightarrow w_{2})\in P:\left|w_{1}\right|\leq \left|w_{2}\right|$.

Man schreibt $G\in {\mbox{Typ}}_{1}$.

Sie erzeugen genau die kontextsensitiven Sprachen, d. h. jede Typ-1-Grammatik erzeugt eine kontextsensitive 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 \gamma \beta$ Wörter bestehend aus Terminalen ($\Sigma$) und Nichtterminalen ($N$) 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 \varepsilon$ ausgehend vom Startsymbol $S$ enthalten darf. Diese Regel wird eventuell benötigt, um das leere Wort $\varepsilon$ ableiten zu können. Die Regel $S\rightarrow \varepsilon$ darf aber nur dann verwendet werden, wenn das Startsymbol $S$ auf keiner rechten Seite der Produktionsregeln auftritt.

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen linear beschränkten Turingmaschine 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).

Im Unterschied zu kontextfreien Grammatiken ist die Anzahl der Variablen (egal ob Terminal oder Nicht-Terminal) auf der linken Seite bei einer kontextsensitiven Grammatik > 1. Einzige Ausnahme: $S\rightarrow \varepsilon$

Typ-2-Grammatik (kontextfreie Grammatik)

Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es handelt sich dabei um Typ-1-Grammatiken mit $\forall (w_{1}\rightarrow w_{2})\in P:w_{1}\in N$.

Man schreibt $G\in {\mbox{Typ}}_{2}$.

Sie 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. (Um das leere Wort $\varepsilon$ zu erzeugen, darf hier für $\gamma$ auch $\varepsilon$ verwendet werden.)

Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen.

Siehe auch: Backus-Naur-Form

Typ-3-Grammatik (rechtslineare bzw. linkslineare Grammatik)

Typ-3-Grammatiken werden auch reguläre Grammatiken genannt. Es handelt sich dabei um Typ-2-Grammatiken mit $\forall (w_{1}\rightarrow w_{2})\in P:w_{1}\in N$ und $w_{2}\in \Sigma \cup \Sigma \cdot N\cup \{\varepsilon \}$.

Man schreibt $G\in {\mbox{Typ}}_{3}$.

Sie 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 entweder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell gefolgt von einem Nichtterminal bestehen (rechtsreguläre Grammatik) oder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell mit vorangestelltem Nichtterminal bestehen (linksreguläre Grammatik)...

Zu jeder linksregulären Grammatik gibt es auch eine rechtsreguläre Grammatik (und umgekehrt), welche die selbe Sprache erzeugt.

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.

Chomsky-Hierarchie für formale Sprachen

Es sei $\Sigma$ ein Alphabet. Eine formale Sprache $L$ ist vom Typ $i\in \{0,...,3\}$, falls es eine Grammatik $G\in {\mbox{Typ}}_{i}$ mit $L=L\left(G\right)$ gibt. Man schreibt dann $L\in {\mathcal {L}}_{i}$.

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.

Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten Sprachen:

${\mathcal {L}}_{3}\subset {\mathcal {L}}_{2}\subset {\mathcal {L}}_{1}\subset {\mathcal {L}}_{0}$

wobei gelegentlich auch folgende Symbole verwendet werden:

$REG\subset CF\subset CS\subset RE$

Übersicht

Die folgende Tabelle fasst die vier Grammatiktypen, die Form ihrer Regeln, die Sprachen die sie erzeugen und die Automatentypen die sie erkennen zusammen. Zudem wird die Abgeschlossenheit der erzeugten Sprachen bezüglich einiger Operationen angegeben.

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

Wobei C = Komplementbildung, K = Konkatenation, S = Schnitt, V = Vereinigung und * = Kleenscher Abschluss

Menschliche Sprachen

Von den formalen Sprachen werden die menschlichen Sprachen unterschieden. Um jedoch maschinelle Übersetzung, Expertensysteme und ähnliches zu ermöglichen, muss menschliche Sprache als formale Sprache dargestellt werden.

Ließe sich für eine menschliche Sprache eine Grammatik vom Typ 2 oder 3 aufstellen, so könnte diese auf einem Computer effizient ausgeführt werden. Wäre menschliche Sprache vom Typ 0, so wäre sie unlösbar (da es keine Computer gibt, die diese Aufgabe in endlicher Zeit bearbeiten können). Eine Hypothese besagt, dass die menschliche Sprache schwach kontext-sensitiv ist (d. h. der Großteil menschlicher Sprache lässt sich kontextfrei darstellen, einige Aspekte jedoch benötigen eine kontextsensitive Repräsentation, ohne dass die Mächtigkeit von Typ-1-Grammatiken dabei ausgeschöpft wird).

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
• Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, B. G. Teubner Stuttgart 1992, ISBN 3-519-02937-5