Chomsky-Hierarchie

Chomsky-Hierarchie (auch: Chomsky–Schützenberger-Hierarchie) ist ein Begriff aus der Theoretischen Informatik und bezeichnet 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. Jedoch sind die Grammatiken im allgemeinen keine Untermengen voneinander.

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 0 bis Typ 3 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 Produktionsregeln und $S$ das Startsymbol dar (Einzelheiten siehe unter formale Grammatik).

Ü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$ $A \in N, \alpha, \beta, \gamma \in V^*, \gamma \neq \epsilon$	kontextsensitiv	linear platzbeschränkte nichtdeterministische Turing-Maschine	CKSV*	-	Typ-2	$A \rightarrow \gamma$ $A \in N, \gamma \in V^*$	kontextfrei	nichtdeterministischer Kellerautomat	KV*	-	Typ-3	$A \rightarrow aB$ (rechtsregulär) oder $A \rightarrow Ba$ (linksregulär) $A \rightarrow a$ $A,B \in N, a \in \Sigma$	regulär	(deterministischer) Endlicher Automat	CKSV*

Mengensymbole

$\Sigma$ : Menge der Terminale
$N$ : Menge der Nichtterminale
$V=\Sigma \cup N$ : Menge der Variablen

Abgeschlossenheit

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 semi-entscheidbare 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| \le \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. Diese Eigenschaft wird oft Längenbeschränktheit genannt.

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 kann die Anzahl der Symbole auf der linken Seite einer kontextsensitiven Grammatik > 1 sein.

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 bildet 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, das heißt, 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 (rechtslineare 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 (linkslineare Grammatik) …

Zu jeder linkslinearen Grammatik gibt es auch eine rechtslineare 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$

Natürliche Sprachen

Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der natürlichen Sprachen zu finden, ist bis heute der Nachweis einer (formalen) Grammatik nur für die wenigsten Sprachen gelungen, die meisten davon konstruierte Plansprachen. Das Problem besteht vor allem in der Mehrdeutigkeit menschlicher Kommunikation mit ihren verschiedenen Bedeutungsebenen. So kann der Satz "Er macht einen Haufen Mist." im wörtlichen als auch im übertragenen Sinne interpretiert werden. Die korrekte Bedeutung ergibt sich aus dem erweiterten Kontext, in dem dieser Satz steht oder kann sogar unaufgelöst bleiben. Selbst um die Mehrdeutigkeit überhaupt erst erkennen zu können, benötigt man einen kulturellen Hintergrund, der ebenfalls nicht mathematisch darstellbar ist.

Die heutigen Übersetzungssysteme umgehen diese Formalisierung und nutzen Datenbanken mit Redewendungen, die den jeweiligen Kontext mitliefern. Die Übersetzung bleibt mechanisch. Die Bedeutung muss der Leser selbst dem Text entlocken. Da wir keine Schwierigkeiten haben bei der inhaltlichen Erfassung von Texten, wenn nur die Vokabeln stimmen, ist auf diese Weise ganz ohne Expertensystem eine praktikable automatische Übersetzung möglich geworden.

Literatur

Noam Chomsky: Three models for the description of language. In: IRE Transactions on Information Theory 2 (1956), S. 113–124
Noam Chomsky: On certain formal properties of grammars. In: Information and Control 1 (1959), S. 91–112
Noam Chomsky, Marcel P. Schützenberger: The algebraic theory of context free languages, Computer Programming and Formal Languages (P. Braffort and D. Hirschberg ed.), North Holland, Amsterdam, 1963, 118-161.
Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit. B. G. Teubner, Stuttgart 1992, ISBN 3-519-02937-5

Formale Sprachen | Theoretische Informatik | Compilerbau

Gourt Home::Gourt :: Chomsky-Hierarchie