Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der theoretischen Informatik. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind; bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt.

Grammatiken niedrigeren Typs sind erzeugungsmächtiger als die höherer Typen. Eine Sprache, die von einer Grammatik des Typs k erzeugt wird, heißt eine Sprache des Typs k. Neben die Chomsky-Hierarchie der Grammatiken tritt in diesem Sinne eine Chomsky-Hierarchie der Sprachen.

Hintergründe

Formale Sprachen haben den Vorzug, mathematisch exakt analysiert werden zu können. Formalen Sprachen liegt ein vorgegebenes Alphabet (ein Zeichenvorrat) zugrunde, das häufig mit ${\displaystyle \Sigma }$ bezeichnet wird. Beliebig lange, endliche Folgen von Elementen des Alphabets werden als Wörter über dem Alphabet bezeichnet. Mengen solcher Wörter sind schließlich formale Sprachen. Die umfassendste formale Sprache über einem vorgegebenen Alphabet ${\displaystyle \Sigma }$ ist unendlich groß; sie enthält sämtliche Wörter, die durch beliebiges Zusammenfügen von Zeichen des Alphabets gebildet werden können. Sie lässt sich durch die Kleenesche Hülle des Alphabets beschreiben, also ${\displaystyle \Sigma ^{*}}$. Die kleinste formale Sprache enthält gar keine Wörter. Andere formale Sprachen bestehen nur aus wenigen Wörtern und lassen sich somit als endliche Menge notieren; beispielsweise für das Alphabet ${\displaystyle \textstyle \Sigma =\{a,b\}}$ die Sprache aller Wörter der Länge zwei: ${\displaystyle \textstyle L=\{aa,ab,ba,bb\}}$.

Unendliche Sprachen lassen sich begreiflicherweise nicht durch Aufzählen notieren. Um sie exakt zu beschreiben, ist ein Konzept nötig, das auch unendliche Mengen definieren kann. Hierzu werden im Rahmen der formalen Sprachen vor allem Erzeugungsverfahren benutzt.

Geht man von einem vorhandenen Wort über einem Alphabet aus, lassen sich durch Semi-Thue-Systeme Wortmengen spezifizieren, die sich durch beliebig wiederholtes Anwenden von Ersetzungsregeln ergeben. Ersetzungsregeln der Form ${\displaystyle \alpha \rightarrow \beta }$ erlauben, dass in einem Wort, das ein Segment ${\displaystyle \alpha }$ enthält, dieses Segment durch ${\displaystyle \beta }$ ersetzt wird. Semi-Thue-Systeme geben daher eine Ableitungsrelation zwischen Wörtern formaler Sprachen an: Zwei Wörter stehen in Relation, wenn das eine Wort durch eine Ersetzungsregel vom anderen Wort abgeleitet werden kann.

Zur Beschreibung von formalen Sprachen eignen sich formale Grammatiken, ein gegenüber Semi-Thue-Systemen erweitertes und mächtigeres Konzept. Sie unterscheiden sich von Semi-Thue-Systemen darin, dass sie sogenannte Terminalsymbole und Nichtterminalsymbole kennen. Terminalsymbole einer Grammatik sind gerade alle Zeichen ihres Zeichensatzes ${\displaystyle \Sigma }$. Die erste anwendbare Regel geht immer von einem nichtterminalen Startsymbol aus, und das Ergebnis eines Ersetzungsvorgangs gilt nur dann als Wort ihrer formalen Sprache, wenn es keine Nichtterminalsymbole enthält.

Das folgende Beispiel beschreibt eine Sprache, mit der sich beliebig lange Summen der Ziffern 1, 2 und 3 ausdrücken lassen. Das dafür angemessene Alphabet ist ${\displaystyle \Sigma =\{+,1,2,3\}}$. Die entsprechenden Terminalsymbole sind unterstrichen dargestellt, Nicht-Terminale kursiv. Die folgenden Zeilen stellen die Regeln dar.

${\displaystyle {\begin{aligned}{\mathit {Summe}}&\rightarrow {\mathit {Ziffer}}\\{\mathit {Summe}}&\rightarrow {\mathit {Summe}}\ {\underline {+}}\ {\mathit {Ziffer}}\\{\mathit {Ziffer}}&\rightarrow {\underline {1}}\\{\mathit {Ziffer}}&\rightarrow {\underline {2}}\\{\mathit {Ziffer}}&\rightarrow {\underline {3}}\\\end{aligned}}}$

Das Startsymbol dieser Sprache ist Summe. Davon ausgehend kann man nun beliebige Regeln nacheinander anwenden, um einen gültigen Ausdruck zu erzeugen:

${\displaystyle {\begin{aligned}&{\mathit {Summe}}&\quad &{\text{(Startsymbol)}}\\&{\mathit {Summe}}\ {\underline {+}}\ {\mathit {Ziffer}}&&{\text{(mit zweiter Regel)}}\\&{\mathit {Ziffer}}\ {\underline {+}}\ {\mathit {Ziffer}}&&{\text{(mit erster Regel)}}\\&{\underline {1\ +}}\ {\mathit {Ziffer}}&&{\text{(mit 1. Ziffern-Regel)}}\\&{\underline {1+2}}&&{\text{(mit 2. Ziffern-Regel)}}\\\end{aligned}}}$

Nicht alle unendlichen Sprachen lassen sich als formale Sprachen mit diesem Erzeugungsprinzip beschreiben, es ist aber kein tauglicheres Konzept bekannt. Ein anderer gängiger Formalismus zur Beschreibung von Sprachen sind Automatenmodelle, vor allem Turingmaschinen. Uneingeschränkte formale Grammatiken und Turingmaschinen sind bei der Beschreibung von formalen Sprachen gleichmächtig, d. h. zu jeder von einer formalen Grammatik erzeugten Sprache gibt es eine Turingmaschine, die genau diese akzeptiert, und umgekehrt.

Ebenso wie verschiedene Automatenmodelle definiert wurden, definierte Chomsky in seiner Arbeit verschiedene Grammatiktypen. Durch drei fortlaufend schärfere Einschränkungen an die jeweils darin zulässigen Ersetzungsregeln stellte er eine Hierarchie aus vier Klassen von formalen Grammatiken auf, wodurch die weniger eingeschränkten Klassen die stärker regulierten Klassen jeweils echt umfassen. Das Gleiche gilt für die von den jeweiligen Grammatikklassen beschriebenen Sprachklassen: auch sie bilden eine Hierarchie.

Sprachen eingeschränkteren Grammatiktyps sind üblicherweise einfacher algorithmisch zu verarbeiten – um den Preis, weniger ausdrucksmächtig zu sein. Reguläre Ausdrücke, mit denen man etwa Muster für die Suche in Texten definiert, entsprechen zum Beispiel den sehr eingeschränkten Chomsky-Grammatiken des Typs 3 (reguläre Grammatiken) und solche Textsuchen sind effektiv und schnell. Dagegen taugen Grammatiken des Typs 3 wegen ihrer Einfachheit nicht zur Beschreibung von Programmiersprachen, für die man meist weniger eingeschränkte Typ-2-Grammatiken benutzt.

Die Hierarchie

Die Chomsky-Hierarchie umfasst vier Typen formaler Grammatiken, gezählt von 0 bis 3. Typ 0 umfasst alle formalen Grammatiken überhaupt, also ohne Einschränkung an die Gestalt zulässiger Erzeugungsregeln. Grammatiken des Typs 1 bis Typ 3 sind dann zunehmend stärker eingeschränkt. Allein nach Definition ist eine Grammatik vom Typ 1 auch vom Typ 0, eine Grammatik vom Typ 2 auch vom Typ 1, eine Grammatik vom Typ 3 auch vom Typ 2; die Umkehrungen gelten nicht. Deshalb bilden diese Klassen eine echte Hierarchie. Bei den entsprechenden Sprachklassen zeigen Gegenbeispiele, dass ebenfalls die Umkehrungen nicht gelten, weshalb auch sie eine echte Hierarchie bilden.

Chomsky forderte für Typ-1-, Typ-2- und Typ-3-Grammatiken, dass die rechte Seite von Produktionsregeln nicht kürzer als die linke Seite sein darf, was auch das leere Wort auf jeder rechten Seite einer Produktionsregel ausschließt. Heute ist man oft weniger restriktiv; die Definitionen sind oft so gefasst, dass die Hierarchie der Sprachen nicht gestört wird, sie es aber auch Grammatiken des Typs 1 (kontextsensitive Grammatiken) durch eine Ausnahmeregel erlauben, das leere Wort zu erzeugen, und den Typen 2 (kontextfreien Grammatiken) und 3 (regulären Grammatiken) sogar ohne Einschränkung das leere Wort als rechte Seite von Ersetzungsregeln gestatten.

Übersicht

Die folgende Tabelle führt für die vier Grammatiktypen auf, welche Form ihre Regeln haben, welchen Namen die erzeugten Sprachen haben und welche Automatentypen diese Sprachen erkennen, also das Wortproblem zumindest semi-entscheiden (Wort in Sprache: Maschine hält in akzeptierendem Endzustand, Wort nicht in Sprache: Maschine hält nie oder hält in nicht akzeptierendem Zustand → sicher hält die Maschine also nur, wenn das Wort in der Sprache ist). Da in der Chomsky-Hierarchie für die Sprachmengen aber eine echte Teilmengenbeziehung gilt (siehe nächster Abschnitt) entscheiden z. B. Turingmaschinen selbstverständlich ebenfalls das Wortproblem für Sprachen vom Typ 1 bis 3. (entscheiden heißt: Wort in Sprache: Maschine hält in akzeptierendem Endzustand, Wort nicht in Sprache: Maschine hält in nicht akzeptierendem Zustand → irgendwann hält die Maschine und das Problem (Wort in Sprache?) ist entschieden) Außerdem wird vermerkt, gegenüber welchen Operationen die erzeugten Sprachen abgeschlossen sind.

Grammatik	Regeln	Sprachen	Entscheidbarkeit	Automaten	Abgeschlossenheit	Zeitabschätzung
Typ-0 Beliebige formale Grammatik	${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle \alpha \in V^{*}\setminus T^{*},\beta \in V^{\ast }}$	rekursiv aufzählbar (nicht „nur“ rekursiv, die wären entscheidbar!)	–	Turingmaschine (egal ob deterministisch oder nicht-deterministisch)	${\displaystyle \circ ,\cap ,\cup ,\ast }$	unbeschränkt
Typ-1 Kontextsensitive Grammatik	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ ${\displaystyle A\in N,\alpha ,\beta \in V^{\ast },\gamma \in V^{+}\;}$ ${\displaystyle S\rightarrow \varepsilon }$ ist erlaubt, wenn es keine Regel ${\displaystyle \alpha \rightarrow \beta S\gamma }$ in ${\displaystyle P}$ gibt.	kontextsensitiv	Wortproblem	linear platzbeschränkte nichtdeterministische Turingmaschine	${\displaystyle \complement ,\circ ,\cap ,\cup ,\ast }$	${\displaystyle O(2^{n})}$
Typ-2 Kontextfreie Grammatik	${\displaystyle A\rightarrow \gamma }$ ${\displaystyle A\in N,\gamma \in V^{\ast }}$	kontextfrei	Wortproblem, Leerheitsproblem, Endlichkeitsproblem	nichtdeterministischer Kellerautomat	${\displaystyle \circ ,\cup ,\ast }$	${\displaystyle O(n^{3})}$
Typ-3 Reguläre Grammatik	${\displaystyle A\rightarrow aB}$ (rechtsregulär) oder ${\displaystyle A\rightarrow Ba}$ (linksregulär) ${\displaystyle A\rightarrow a}$ ${\displaystyle A\rightarrow \varepsilon }$ ${\displaystyle A,B\in N,a\in T}$ Nur links- oder nur rechtsreguläre Produktionen	regulär	Wortproblem, Leerheitsproblem, Endlichkeitsproblem, Äquivalenzproblem	Endlicher Automat (egal ob deterministisch oder nicht-deterministisch)	${\displaystyle \complement ,\circ ,\cap ,\cup ,\ast }$	${\displaystyle O(n)}$

Legende für die Spalte Regeln

• ${\displaystyle T}$ … endliches Alphabet (Menge der Terminalsymbole, oft auch mit ${\displaystyle \Sigma }$ bezeichnet, das aber auch ${\displaystyle V\cup N}$ bedeuten kann)
• ${\displaystyle N}$ … die davon disjunkte Menge der Nichtterminalsymbole (gelegentlich auch Variablen genannt und mit ${\displaystyle V}$ bezeichnet, statt ${\displaystyle V:=N\cup T}$ … gesamtes Vokabular)
• ${\displaystyle S\in N}$ … Startsymbol
• ${\displaystyle \varepsilon }$ … leeres Wort (oft auch mit ${\displaystyle \lambda }$ bezeichnet)
• ${\displaystyle P}$ … Menge von Produktionsregeln (als Teilmenge eines kartesischen Produkts eine Relation)
• ${\displaystyle \setminus }$ … Mengen-Differenzbildung
• ${\displaystyle ^{\ast }}$ … Kleenescher Abschluss (Hülle), siehe Kleenesche und positive Hülle
• ${\displaystyle ^{+}}$ … positive Hülle, z. B. meint ${\displaystyle \gamma \in (T\cup N)^{+}=V^{+}}$ … ${\displaystyle \gamma }$ muss mindestens ein Symbol (Terminal oder ein Nichtterminal) enthalten

In der obigen Tabelle werden somit mit lateinischen Großbuchstaben Nichtterminalsymbole dargestellt ${\displaystyle A,B\in N}$, mit lateinischen Kleinbuchstaben Terminalsymbole ${\displaystyle a\in T}$ und griechische Kleinbuchstaben werden verwendet, wenn es sich sowohl um Nichtterminal als auch um Terminalsymbole handeln kann.

Achtung: Bei ${\displaystyle ^{\ast }}$ und ${\displaystyle ^{+}}$ kann ein griechischer Kleinbuchstabe für Wörter aus mehreren Terminal- oder Nichtterminalsymbolen stehen!

Legende für die Spalte Abgeschlossenheit

• ${\displaystyle \complement }$ … Komplementbildung
• ${\displaystyle \circ }$ … Konkatenation
• ${\displaystyle \cap }$ … Schnittmenge
• ${\displaystyle \cup }$ … Vereinigungsmenge
• ${\displaystyle ^{\ast }}$ … Kleenescher Abschluss (Hülle)

Chomsky-Hierarchie für formale Sprachen

Eine formale Sprache ist vom Typ ${\displaystyle i}$ entsprechend der Hierarchie für Grammatiken, wenn es von einer Typ-${\displaystyle i}$-Grammatik erzeugt wird. Formal ausgedrückt heißt das: ${\displaystyle L}$ ist vom Typ ${\displaystyle i\in \{0,\ldots ,3\},}$ falls es eine Grammatik ${\displaystyle G\in {\mbox{Typ}}_{i}}$ mit ${\displaystyle L=L\left(G\right)}$ gibt. Man schreibt dann ${\displaystyle L\in {\mathcal {L}}_{i}.}$

In der Chomsky-Hierarchie für formale Sprachen besteht zwischen den Sprachmengen benachbarter Ebenen eine echte Teilmengenbeziehung. Jede kontextsensitive Sprache ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Sprachen, die nicht kontextsensitiv sind. Ebenso ist jede kontextfreie Sprache auch kontextsensitiv, aber nicht umgekehrt, und jede reguläre Sprache ist kontextfrei, aber nicht jede kontextfreie Sprache ist regulär.

Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten Sprachen: ${\displaystyle {\mathcal {L}}_{3}\subset {\mathcal {L}}_{2}\subset {\mathcal {L}}_{1}\subset {\mathcal {L}}_{0},}$ wobei gelegentlich auch folgende Symbole verwendet werden: ${\displaystyle \mathrm {REG} \subset \mathrm {CF} \subset \mathrm {CS} \subset \mathrm {RE.} }$

Beispiele für Sprachen in den jeweiligen Differenzmengen sind:

• ${\displaystyle L_{1}=\left\{a^{n}b^{n}c^{n}\,|\,n\geq 1\right\}}$ ist vom Typ 1, aber nicht vom Typ 2
• ${\displaystyle L_{2}=\left\{a^{n}b^{n}\,|\,n\geq 1\right\}}$ ist vom Typ 2, aber nicht vom Typ 3

Beweise für die Nichtzugehörigkeit bestimmter Sprachen zu den Sprachklassen ${\displaystyle {\mathcal {L}}_{2}}$ und ${\displaystyle {\mathcal {L}}_{3}}$ wie hier werden oft mit dem Schleifensatz geführt.

Natürliche Sprachen

Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der natürlichen Sprachen zu finden, ist bis heute für keine natürliche Sprache der Nachweis einer korrekten und vollständigen formalen Grammatik gelungen. Das Problem besteht u. a. im Zusammenspiel der verschiedenen Grammatikteile, die jeweils einzelne sprachliche Phänomene modellieren. Aber auch beim praktischen Einsatz formaler Grammatiken in der Computerlinguistik kann es zu Mehrdeutigkeiten auf verschiedenen Ebenen der Sprachbetrachtung kommen; diese müssen (z. B. in der maschinellen Übersetzung) anhand des Kontextes aufgelöst werden.

Literatur

• Noam Chomsky: Three models for the description of language. In: IRE Transactions on Information Theory. Vol.2, 1956, S. 113–124 (chomsky.info [PDF]). 
• Noam Chomsky: On certain formal properties of grammars. In: Information and Control. Vol.2, 1959, S. 137–167 (diku.dk [PDF]). 
• Noam Chomsky, Marcel P. Schützenberger: The algebraic theory of context free languages, Computer Programming and Formal Languages. Hrsg.: P. Braffort, D. Hirschberg. North Holland, Amsterdam 1963, S. 118–161. 
• Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5. 

Einzelnachweise

1. ↑ Im Zusammenhang mit formalen Grammatiken wird hier für das ‚Zielalphabet’ der Terminalsymbole das Zeichen ${\displaystyle T}$ statt – wie sonst - ${\displaystyle \Sigma }$ verwendet. Achtung: Manche Autoren bezeichnen mit ${\displaystyle \Sigma }$ abweichend das Gesamtvokabular ${\displaystyle N\cup T}$ (hier mit ${\displaystyle V}$ bezeichnet).
2. ↑ Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 81. 
3. ↑ John Spacey: Natural Language vs. Formal Language. In: Simplicable. 12. April 2017, abgerufen am 6. September 2021 (englisch).