134.245.44.20: /* Übersicht / : Typ-2-Sprachen wären nach vorheriger Definition nicht monoton, "" zu "+" korrigiert.

2025-05-05T08:42:50Z

Übersicht: : Typ-2-Sprachen wären nach vorheriger Definition nicht monoton, "*" zu "+" korrigiert.

Neue Seite

'''Chomsky-Hierarchie''', gelegentlich '''Chomsky-Schützenberger-Hierarchie''' (benannt nach dem Linguisten [[Noam Chomsky]] und dem Mathematiker [[Marcel Schützenberger]]), ist ein Begriff aus der [[Theoretische Informatik|theoretischen Informatik]]. Sie ist eine [[Hierarchie]] von [[Klasse (Mengenlehre)|Klassen]] [[Formale Grammatik|formaler Grammatiken]], die [[formale Sprache]]n erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die Hierarchiestufen unterscheiden sich darin, wie [[Rigidität (Informatik)|rigide]] die Einschränkungen für die Form zulässiger [[Produktionsregel]]n 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 (Informatik)|Alphabet]]'' (ein Zeichenvorrat) zugrunde, das häufig mit <math>\Sigma</math> bezeichnet wird. Beliebig lange, endliche Folgen von Elementen des Alphabets werden als ''[[Wort (Theoretische Informatik)|Wörter]]'' über dem Alphabet bezeichnet. Mengen solcher Wörter sind schließlich ''formale Sprachen''. Die umfassendste formale Sprache über einem vorgegebenen Alphabet <math>\Sigma</math> 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 und positive Hülle|Kleenesche Hülle]] des Alphabets beschreiben, also <math>\Sigma^*</math>. 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 <math>\textstyle \Sigma=\{a,b\}</math> die Sprache aller Wörter der Länge zwei: <math>\textstyle L=\{aa,ab,ba,bb\}</math>.

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-System]]e Wortmengen spezifizieren, die sich durch beliebig wiederholtes Anwenden von ''Ersetzungsregeln'' ergeben. Ersetzungsregeln der Form <math>\alpha\rightarrow\beta</math> erlauben, dass in einem Wort, das ein Segment <math>\alpha</math> enthält, dieses Segment durch <math>\beta</math> 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 [[Terminalsymbol]]e und [[Nichtterminalsymbol]]e kennen. Terminalsymbole einer Grammatik sind gerade alle Zeichen ihres Zeichensatzes <math>\Sigma</math>. 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 <math>\Sigma=\{+,1,2,3\}</math>. Die entsprechenden Terminalsymbole sind unterstrichen dargestellt, Nicht-Terminale kursiv. Die folgenden Zeilen stellen die Regeln dar.

:<math>
\begin{align}
\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{align}
</math>

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

:<math>
\begin{align}
& \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{align}
</math>

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 [[Automat (Informatik)|Automatenmodelle]], vor allem [[Turingmaschine]]n. Uneingeschränkte [[formale Grammatik]]en 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ärer Ausdruck|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 [[Leeres Wort|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.

=== {{Anker|Typ-0-Grammatik}}Typ-0-Grammatik (allgemeine Chomsky-Grammatik oder Phrasenstrukturgrammatik) ===
{{Hauptartikel|Formale Grammatik}}

==== Definition ====
Typ-0-Grammatiken werden auch ''unbeschränkte'' Grammatiken genannt. Es handelt sich dabei um die Klasse aller formalen Grammatiken der Form
<math>G =</math> [[Tupel|<math>(V,T,P,S)</math>]], wobei <math>V = T \cup N</math> ein ''Vokabular'' ist, bestehend aus der [[disjunkt]]en Vereinigung eines endlichen Alphabets <math>T</math> (Terminalsymbole) und einer Menge von Nichtterminalen (Variablen) <math>N</math>.<ref>Im Zusammenhang mit formalen Grammatiken wird hier für das ‚Zielalphabet’ der Terminalsymbole das Zeichen <math>T</math> statt – wie sonst - <math>\Sigma</math> verwendet. Achtung: Manche Autoren bezeichnen mit <math>\Sigma</math> abweichend das '''Gesamt'''vokabular <math>N \cup T</math> (hier mit <math>V</math> bezeichnet).</ref> Das ausgezeichnete Symbol <math>S \in N</math> wird als ''Startsymbol'' bezeichnet und <math>P</math> ist eine Menge von Produktionsregeln
<math>P \subset</math> [[Differenzmenge|<math>(V^*\setminus{T}^*)</math>]] [[Kartesisches Produkt|<math>\times</math>]] [[Kleenesche Hülle|<math>V^*</math>]] <math>=</math> [[Konkatenation (Formale Sprache)|<math>V^*NV^*</math>]] [[Kartesisches Produkt|<math>\times</math>]] [[Kleenesche Hülle|<math>V^*</math>]], d. h. auf der linken Seite jeder Produktionsregel steht wenigstens ein Nicht-Terminalsymbol. Für einzelne Regeln schreibt man anstelle von  <math>(\alpha,\beta)\in P</math>  meistens <math>\alpha\rightarrow\beta</math>, für die Menge der Regeln mit <math>\alpha</math> auf der linken Seite  <math>\{(\alpha,\beta_1),\dots,(\alpha,\beta_n)\} \subseteq P</math>  auch  <math>\alpha\rightarrow\beta_1\mid\dots\mid\beta_n</math>.

Um die Zugehörigkeit zur Klasse der Typ-0-Grammatiken auszudrücken, schreibt man <math>G \in \mbox{Typ}_0.</math>

==== 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ählbare Sprache|rekursiv aufzählbaren Sprachen]] (oft auch ''[[Semi-entscheidbare Menge|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 [[Rekursive Sprache|rekursiven Sprachen]] (oft auch ''entscheidbare Sprachen'' genannt) unterscheidet, welche durch Turingmaschinen ''entschieden'' werden können.

=== Typ-1-Grammatik (kontextsensitive Grammatik) ===
{{Hauptartikel|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 <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> oder <math>S \rightarrow \varepsilon</math> haben, wobei <math>A</math> ein Nichtterminal und <math>\alpha, \gamma, \beta</math> Wörter bestehend aus Terminalen (<math>T</math>) und Nichtterminalen (<math>N</math>) sind. <math>\varepsilon</math> bezeichnet das leere Wort. Die Wörter <math>\alpha</math> und <math>\beta</math> können leer sein, aber <math>\gamma</math> 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 <math>S \rightarrow \varepsilon</math> 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 [[Ableitung (Informatik)#Satzform|Satzform]] länger wird oder gleich lang bleibt.

Ist eine Grammatik <math>G</math> kontextsensitiv, so schreibt man <math>G \in \mbox{Typ}_1</math>.

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 [[Kontextsensitive Sprache|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 [[Nichtdeterministische Turingmaschine|nichtdeterministischen]], [[Linear beschränkte Turingmaschine|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 <math>a</math>, sodass das Band der Turingmaschine höchstens <math>a \cdot x</math> Felder besitzt, wobei <math>x</math> die Länge des Eingabewortes ist).

==== Monotone Grammatiken ====
Einige Autoren bezeichnen eine Grammatik schon dann als kontextsensitiv, wenn bis auf die Ausnahme <math>S\rightarrow\varepsilon</math> (s. o.) alle Produktionsregeln <math>w_1 \rightarrow w_2</math> nur die Bedingung <math>\left|w_1\right| \leq \left|w_2\right|</math> 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 [[Monotone Grammatik|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) ===
{{Hauptartikel|Kontextfreie Grammatik}}

==== Definition ====
Typ-2-Grammatiken werden auch ''kontextfreie Grammatiken'' genannt. Es sind Grammatiken, für die gelten muss: <math>\forall (w_1 \rightarrow w_2) \in P: ( w_1 \in N) \land \left(w_2 \in V^+\right).</math> 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 <math>V = N \cup T</math> stehen.

Außerdem kann wie bei Typ-1-Grammatiken die Ausnahmeregel <math>S\rightarrow\varepsilon</math> zugelassen werden, wenn <math>S</math> auf keiner rechten Seite einer Regel vorkommt.

Man schreibt <math>G \in \mbox{Typ}_2.</math>

Kontextfreie Grammatiken werden oft so definiert, dass die rechte Seite auch leer sein darf, also <math>(w_1 \rightarrow \varepsilon) \in P</math>. Solche Grammatiken erfüllen nicht mehr alle Eigenschaften von Typ-2-Grammatiken und stünden nicht mehr in der von Chomsky definierten Hierarchie. Sie erfüllen aber die Bedingungen von monotonen Grammatiken.

==== Von Typ-2-Grammatiken erzeugte Sprachen ====
Kontextfreie Grammatiken (mit <math>\varepsilon</math>-Ausnahmeregel) erzeugen genau die [[Kontextfreie Sprache|kontextfreien Sprachen]], jede Typ-2-Grammatik erzeugt also eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt.

Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen [[Kellerautomat]]en (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bildet die theoretische Basis für die Syntax der meisten [[Programmiersprache]]n.

Siehe auch: [[Backus-Naur-Form]] (BNF) / [[Erweiterte Backus-Naur-Form]] (EBNF): ein anderes, äquivalentes Schema der Bezeichnungsweisen.

=== Typ-3-Grammatik (reguläre Grammatik) ===
{{Hauptartikel|Reguläre Grammatik}}

==== Definition ====
Typ-3-Grammatiken werden auch ''reguläre Grammatiken'' genannt. Es handelt sich um Typ-2-Grammatiken, bei denen auf der rechten Seite von Produktionen genau ein Terminalsymbol auftreten darf und maximal ein weiteres Nichtterminalsymbol. Die erlaubte Stellung solcher Nichtterminalsymbole muss außerdem über alle Produktionen hinweg einheitlich ''immer vor'' oder ''immer hinter'' dem Terminalsymbol sein, je nachdem spricht man auch genauer von ''linksregulären'' und ''rechtsregulären Grammatiken''. Sie stimmen mit den links- beziehungsweise rechts-linearen Grammatiken überein, wohingegen [[lineare Grammatik]]en nicht den regulären Grammatiken entsprechen.

Für ''linksreguläre'' Typ-3-Grammatiken muss also die Bedingung erfüllt sein, dass

<math>\forall (w_1 \rightarrow w_2) \in P: (w_1 \in N) \land</math> <math>(w_2 \in T \cup NT)</math>.

Sie dürfen also nur ''links''reguläre Produktionen (Nichtterminalsymbol auf der rechten Seite in ''Vorder''stellung) enthalten.

Üblicherweise gestattet man für reguläre Grammatiken, wie auch für kontextfreie Grammatiken Regeln mit leerer rechter Seite, also
<math>(w_1\rightarrow\varepsilon) \in P</math>.

''Rechtsreguläre Grammatiken'' erfüllen dagegen die analoge Bedingung

<math>\forall (w_1 \rightarrow w_2) \in P: (w_1 \in N) \land</math> <math>(w_2 \in T \cup TN \cup \{ \varepsilon \})</math>.

Diese enthalten also nur ''rechts''reguläre Produktionen (Nichtterminalsymbol auf der rechten Seite allenfalls in ''Hinter''stellung). Diese Bedingung drückt auch schon die Erlaubnis leerer rechter Seiten aus.

Linksreguläre und rechtsreguläre Grammatiken erzeugen genau dieselbe Sprachklasse, es gibt also zu jeder linksregulären Grammatik auch eine rechtsreguläre, die dieselbe Sprache erzeugt, und umgekehrt.

Man beachte, dass beim Auftreten von linksregulären ''und'' rechtsregulären Produktionen in ein und derselben Chomsky-Grammatik diese ''nicht'' regulär ist. Die Grammatiken mit sowohl linksregulären als auch rechtsregulären Produktionen erzeugen nämlich eine echt größere Sprachklasse.

Manche Autoren erlauben in den Definitionen für reguläre / linksreguläre / rechtsreguläre Grammatiken überall dort, wo hier in Produktionen nur ein einzelnes Nichtterminalzeichen stehen darf, auch eine beliebige nichtleere terminale Zeichenkette. An der Erzeugungsmächtigkeit der Klassen ändert sich dadurch nichts.

Man schreibt <math>G \in \mbox{Typ}_3</math> für reguläre Grammatiken <math>G</math>.

==== Von Typ-3-Grammatiken erzeugte Sprachen ====
Reguläre Grammatiken erzeugen genau die [[Reguläre Sprache|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.

Reguläre Sprachen können alternativ auch durch [[Regulärer Ausdruck|reguläre Ausdrücke]] beschrieben werden und die regulären Sprachen sind genau die Sprachen, die von [[Endlicher Automat|endlichen Automaten]] erkannt werden können. Sie werden häufig genutzt, um Suchmuster oder die lexikalische Struktur von Programmiersprachen zu definieren.

=== Ü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-entscheidbare Menge|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 [[Operation (Informatik)|Operationen]] die erzeugten Sprachen [[Abgeschlossenheit (algebraische Struktur)|abgeschlossen]] sind.

{| class="wikitable"
|- class="hintergrundfarbe6"
! Grammatik
! Regeln
! Sprachen
! Entscheidbarkeit
! Automaten
! Abgeschlossenheit<ref>{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik – kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=81}}</ref>
! Zeitabschätzung
|-----
| '''Typ-0''' [[Formale Grammatik|Beliebige formale Grammatik]]
| <math>\alpha \rightarrow \beta</math> 

<math>\alpha \in V^*\setminus T^* , \beta \in V^\ast</math>
| [[Rekursiv aufzählbare Sprache|rekursiv aufzählbar]] (nicht „nur“ [[Rekursive Sprache|rekursiv]], die wären entscheidbar!)
| –
| [[Turingmaschine]] (egal ob deterministisch oder nicht-deterministisch)
| <math>\circ, \cap, \cup, \ast</math>
| unbeschränkt
|-----
| '''Typ-1''' [[Kontextsensitive Grammatik]]
| <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> 

<math>A \in N, \alpha, \beta \in V^\ast, \gamma \in V^+\;</math> 
<math>S \rightarrow \varepsilon</math> ist erlaubt, wenn es keine Regel <math>\alpha \rightarrow \beta S\gamma</math> in <math>P</math> gibt.
| [[Kontextsensitive Sprache|kontextsensitiv]]
| [[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]]
| [[Linear beschränkte Turingmaschine|linear platzbeschränkte nichtdeterministische Turingmaschine]]
| <math>\complement, \circ, \cap, \cup, \ast</math>
|<math>O(2^n)</math>
|-----
| '''Typ-2''' [[Kontextfreie Grammatik]]
| <math>A \rightarrow \gamma</math> 

<math>A \in N, \gamma \in V^+</math> 
| [[Kontextfreie Sprache|kontextfrei]]
| [[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]], [[Leerheitsproblem]], [[Endlichkeitsproblem]]
| nichtdeterministischer [[Kellerautomat]]
| <math>\circ, \cup, \ast</math>
| <math>O(n^3)</math>
|-----
| '''Typ-3''' [[Reguläre Grammatik]]
| <math>A \rightarrow aB</math> (rechtsregulär) oder <math>A \rightarrow Ba</math> (linksregulär) <math>A \rightarrow a</math> <math>A \rightarrow \varepsilon</math> <math>A,B \in N, a \in T</math> 
Nur links- oder nur rechtsreguläre Produktionen
| [[Reguläre Sprache|regulär]]
| [[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]], [[Leerheitsproblem]], [[Endlichkeitsproblem]], [[Äquivalenzproblem]], [[Schnittproblem]]
| [[Endlicher Automat]] (egal ob deterministisch oder nicht-deterministisch)
| <math>\complement, \circ, \cap, \cup, \ast</math>
| <math>O(n)</math>
|}

;Legende für die Spalte ''Regeln''
* <math>T</math> … endliches ''Alphabet'' (Menge der Terminalsymbole, oft auch mit <math>\Sigma</math> bezeichnet, das aber auch <math>V \cup N</math> bedeuten kann)
* <math>N</math> … die davon [[disjunkt]]e Menge der Nichtterminalsymbole (gelegentlich auch ''Variablen'' genannt und mit <math>V</math> bezeichnet, statt <math>V := N \cup T</math> … gesamtes ''Vokabular'')
* <math>S \in N</math> … ''Startsymbol''
* <math>\varepsilon</math> … [[leeres Wort]] (oft auch mit <math>\lambda</math> bezeichnet)
* <math>P</math> … Menge von [[Produktionsregel]]n (als [[Teilmenge]] eines [[Kartesisches Produkt|kartesischen Produkts]] eine [[Relation (Mathematik)|Relation]])
* <math>\setminus </math> … [[Differenzmenge|Mengen-Differenzbildung]]
* <math>^{\ast}</math> … Kleenescher Abschluss (Hülle), siehe [[Kleenesche und positive Hülle]]
* <math>^{+}</math> … positive Hülle, z. B. meint <math> \gamma \in (T \cup N)^+ = V^+</math> … <math>\gamma</math> muss mindestens ein Symbol (Terminal oder ein Nichtterminal) enthalten

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

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

;Legende für die Spalte ''Abgeschlossenheit''
* <math>\complement</math> … [[Komplement (Mengenlehre)|Komplementbildung]]
* <math>\circ</math> … [[Konkatenation (Formale Sprache)|Konkatenation]]
* <math>\cap</math> … [[Schnittmenge]]
* <math>\cup</math> … [[Vereinigungsmenge]]
* <math>^{\ast}</math> … [[Kleenesche und positive Hülle|Kleenescher Abschluss]] (Hülle)


== Chomsky-Hierarchie für formale Sprachen ==
[[Datei:Chomsky-Hierarchie.svg|mini|Teilmengenbeziehung der Sprachklassen in der Chomsky-Hierarchie]]

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

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: <math>\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0,</math> wobei gelegentlich auch folgende Symbole verwendet werden: <math>\mathrm{REG} \subset \mathrm{CF} \subset \mathrm{CS} \subset \mathrm{RE.}</math>

Beispiele für Sprachen in den jeweiligen Differenzmengen sind:
* <math>L_1 = \left\{a^n b^n c^n \,|\, n \ge 1\right\}</math> ist vom Typ 1, aber nicht vom Typ 2
* <math>L_2 = \left\{a^n b^n \,|\, n \ge 1\right\}</math> ist vom Typ 2, aber nicht vom Typ 3

Beweise für die Nichtzugehörigkeit bestimmter Sprachen zu den Sprachklassen <math>\mathcal{L}_2</math> und <math>\mathcal{L}_3</math> wie hier werden oft mit dem [[Pumping-Lemma|Schleifensatz]] geführt.

== Natürliche Sprachen ==
{{Belege fehlen}}
Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der [[Natürliche Sprache|natürlichen Sprachen]] zu finden, ist bis heute für keine natürliche Sprache der Nachweis einer [[Korrektheit (Logik)|korrekten]] und [[Vollständigkeit (Logik)|vollständigen]] formalen Grammatik gelungen.<ref>{{Internetquelle |autor=John Spacey |url=https://simplicable.com/new/natural-language-vs-formal-language |titel=Natural Language vs. Formal Language |werk=Simplicable |datum=2017-04-12 |abruf=2021-09-06 |sprache=en}}</ref> 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 [[Mehrdeutigkeit]]en auf verschiedenen Ebenen der Sprachbetrachtung kommen; diese müssen (z. B. in der [[Maschinelle Übersetzung|maschinellen Übersetzung]]) anhand des [[Kontext (Sprachwissenschaft)|Kontextes]] aufgelöst werden.

== Literatur ==
* {{Literatur |Autor=[[Noam Chomsky]] |Titel=Three models for the description of language |Sammelwerk=IRE Transactions on Information Theory |Band=Vol. 2 |Datum=1956 |Seiten=113–124 |Online=https://chomsky.info/wp-content/uploads/195609-.pdf |Format=PDF |KBytes=}}
* {{Literatur |Autor=Noam Chomsky |Titel=On certain formal properties of grammars |Sammelwerk=Information and Control |Band=Vol. 2 |Datum=1959 |Seiten=137–167 |Online=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/chomsky1959.pdf |Format=PDF |KBytes=}}
* {{Literatur |Autor=Noam Chomsky, Marcel P. Schützenberger |Hrsg=P. Braffort, D. Hirschberg |Titel=The algebraic theory of context free languages, Computer Programming and Formal Languages |Verlag=North Holland |Ort=Amsterdam |Datum=1963 |Seiten=118–161}}
* {{Literatur |Autor=Peter Sander, Wolffried Stucky, Rudolf Herschel |Titel=Automaten, Sprachen, Berechenbarkeit |Verlag=Teubner |Ort=Stuttgart |Datum=1992 |ISBN=3-519-02937-5}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4529323-5}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]
[[Kategorie:Noam Chomsky]]

Chomsky-Hierarchie - Versionsgeschichte

134.245.44.20: /* Übersicht */ : Typ-2-Sprachen wären nach vorheriger Definition nicht monoton, "*" zu "+" korrigiert.

134.245.44.20: /* Übersicht / : Typ-2-Sprachen wären nach vorheriger Definition nicht monoton, "" zu "+" korrigiert.