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 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 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 . 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 die Sprache aller Wörter der Länge : .
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 erlauben, dass in einem Wort, das ein Segment enthält, dieses Segment durch 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 . 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 . Die entsprechenden Terminalsymbole sind unterstrichen dargestellt, Nicht-Terminale kursiv. Die folgenden Zeilen stellen die Regeln dar.
Das Startsymbol dieser Sprache ist Summe. Davon ausgehend kann man nun beliebige Regeln nacheinander anwenden, um einen gültigen Ausdruck zu erzeugen:
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.
Typ-0-Grammatik (allgemeine Chomsky-Grammatik oder Phrasenstrukturgrammatik)
Definition Typ-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. Es handelt sich dabei um die Klasse aller formalen Grammatiken der Form , wobei ein Vokabular ist, bestehend aus der disjunkten Vereinigung eines endlichen Alphabets (Terminalsymbole) und einer Menge von Nichtterminalen (Variablen) .Im Zusammenhang mit formalen Grammatiken wird hier für das ‚Zielalphabet’ der Terminalsymbole das Zeichen statt – wie sonst - verwendet. Achtung: Manche Autoren bezeichnen mit abweichend das Gesamtvokabular (hier mit bezeichnet). Das ausgezeichnete Symbol wird als Startsymbol bezeichnet und ist eine Menge von Produktionsregeln , d. h. auf der linken Seite jeder Produktionsregel steht wenigstens ein Nicht-Terminalsymbol. Für einzelne Regeln schreibt man anstelle von meistens , für die Menge der Regeln mit auf der linken Seite auch .
Um die Zugehörigkeit zur Klasse der Typ-0-Grammatiken auszudrücken, schreibt man
Von Typ-0-Grammatiken erzeugte Sprachen Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turingmaschine 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), d. h. die zugehörige Turingmaschine akzeptiert jedes Wort, das in der Sprache liegt. Bei einem Wort, das nicht in der Sprache liegt, kann es sein, dass die Turingmaschine nicht terminiert, d. h. keinerlei Auskunft über die Zugehörigkeit des Worts zur Sprache liefert.
Man beachte, dass sich diese Menge von Sprachen von der Menge der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet, welche durch Turingmaschinen entschieden werden können.
Typ-1-Grammatik (kontextsensitive Grammatik)
Definition Typ-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. Es handelt sich dabei um Typ-0-Grammatiken, bei denen alle Produktionsregeln die Form oder haben, wobei ein Nichtterminal und Wörter bestehend aus Terminalen () und Nichtterminalen () sind. bezeichnet das leere Wort. Die Wörter und können leer sein, aber muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten. Diese Eigenschaft wird Längenbeschränktheit genannt.
Als einzige Ausnahme von dieser Forderung lässt man zu, wenn das Startsymbol nirgends auf der rechten Seite einer Produktion auftritt. Damit erreicht man, dass die kontextsensitiven Sprachen auch das oft erwünschte leere Wort enthalten können, das dann aber immer nur in einer einschrittigen Ableitung aus dem Startsymbol selbst entsteht, und ohne für alle anderen Ableitungen die Eigenschaft zu stören, dass in jedem Teilschritt die Satzform länger wird oder gleich lang bleibt.
Ist eine Grammatik kontextsensitiv, so schreibt man .
Anders als bei kontextfreien Grammatiken können auf der linken Seite der Produktionen kontextsensitiver Grammatiken durchaus statt einzelner Symbole ganze Symbolfolgen stehen, sofern sie mindestens ein Nichtterminalsymbol enthalten.
Von Typ-1-Grammatiken erzeugte Sprachen Die kontextsensitiven Grammatiken erzeugen genau die kontextsensitiven Sprachen. Das heißt: Jede Typ-1-Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt.
Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; das heißt von einer nichtdeterministischen Turingmaschine, deren Band linear durch die Länge der Eingabe beschränkt ist (das bedeutet, es gibt eine konstante Zahl , sodass das Band der Turingmaschine höchstens Felder besitzt, wobei die Länge des Eingabewortes ist).
Monotone Grammatiken Einige Autoren bezeichnen eine Grammatik schon dann als kontextsensitiv, wenn bis auf die Ausnahme (s. o.) alle Produktionsregeln nur die Bedingung erfüllen, d. h., dass die rechte Seite einer solchen Produktion nicht kürzer als deren linke Seite ist. Häufiger findet man dafür jedoch den Begriff der monotonen Grammatik oder der nichtverkürzenden Grammatik.
Es erweist sich, dass die monotonen Grammatiken genau wieder die kontextsensitiven Sprachen erzeugen, weshalb die beiden Klassen von Grammatiken als äquivalent betrachtet werden und manche Autoren nur die eine oder die andere Grammatikklasse überhaupt behandeln. Aber nicht jede monotone Ersetzungsregel ist auch eine kontextsensitive, deshalb ist auch nicht jede monotone Grammatik eine kontextsensitive.
Typ-2-Grammatik (kontextfreie Grammatik)
Definition Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es sind Grammatiken, für die gelten muss: In jeder Regel der Grammatik muss also auf der linken Seite genau ein nicht-terminales Symbol stehen und auf der rechten Seite kann eine beliebige nicht-leere Folge von terminalen und nichtterminalen Symbolen aus dem gesamten Vokabular stehen.
Außerdem kann wie bei Typ-1-Grammatiken die Ausnahmeregel zugelassen werden, wenn auf keiner rechten Seite einer Regel vorkommt.
Man schreibt