Wikipedia · einfach zusammengefasst · Stand
Chomsky-Hierarchie
Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …
Inhalt5 Abschnitte
Kernidee der Chomsky-Hierarchie
Die Chomsky-Hierarchie ist eine Einteilung formaler Grammatiken und der von ihnen erzeugten formalen Sprachen in vier Typen: Typ 0, Typ 1, Typ 2 und Typ 3. Die Typen unterscheiden sich durch die Einschränkungen für die Form ihrer Produktionsregeln. Typ 0 ist uneingeschränkt; von Typ 1 bis Typ 3 werden die Regeln zunehmend stärker beschränkt.
Eine Grammatik eines niedrigeren Typs ist ausdrucksmächtiger als eine Grammatik eines höheren Typs. Daher gilt für die Sprachklassen die echte Teilmengenbeziehung L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀, gelegentlich auch REG ⊂ CF ⊂ CS ⊂ RE. Jede reguläre Sprache ist also kontextfrei, jede kontextfreie Sprache kontextsensitiv und jede kontextsensitive Sprache rekursiv aufzählbar. Die Umkehrungen gelten nicht.
Der Vorteil eingeschränkter Grammatiktypen besteht darin, dass die erzeugten Sprachen meist einfacher und schneller algorithmisch verarbeitet werden können. Reguläre Ausdrücke und endliche Automaten eignen sich beispielsweise für schnelle Textsuche. Für die Syntax der meisten Programmiersprachen werden dagegen meist kontextfreie Grammatiken verwendet.
Formale Sprachen und Grammatiken
Eine formale Sprache basiert auf einem Alphabet Σ, also einem vorgegebenen Zeichenvorrat. Ein Wort ist eine beliebig lange, endliche Folge von Zeichen dieses Alphabets. Eine formale Sprache ist eine Menge solcher Wörter. Die umfassendste Sprache über Σ ist Σ*, die Kleenesche Hülle des Alphabets; sie enthält alle durch beliebiges Zusammenfügen von Zeichen aus Σ gebildeten Wörter. Die kleinste Sprache enthält kein Wort. Für Σ = {a,b} besteht die Sprache aller Wörter der Länge 2 beispielsweise aus L = {aa, ab, ba, bb}.
Unendliche Sprachen können nicht durch vollständiges Aufzählen beschrieben werden. Deshalb verwendet man Erzeugungsverfahren. Semi-Thue-Systeme erlauben Ersetzungsregeln α → β: Enthält ein Wort das Segment α, darf dieses durch β ersetzt werden. Formale Grammatiken erweitern dieses Prinzip um Terminal- und Nichtterminalsymbole. Terminalsymbole sind die Zeichen des Alphabets Σ. Nichtterminalsymbole dienen als Zwischenzeichen. Eine Ableitung beginnt beim Nichtterminalsymbol S, dem Startsymbol. Ein Ergebnis gehört erst dann zur erzeugten Sprache, wenn es keine Nichtterminalsymbole mehr enthält.
Beispielhaft kann die Sprache beliebig langer Summen aus den Ziffern 1, 2 und 3 beschrieben werden. Das Alphabet ist Σ = {+,1,2,3}; die Regeln lauten:
Summe → Ziffer Summe → Summe + Ziffer Ziffer → 1 | 2 | 3
Eine mögliche Ableitung ist Summe ⇒ Summe + Ziffer ⇒ Ziffer + Ziffer ⇒ 1 + Ziffer ⇒ 1 + 2. Das Ergebnis 1+2 enthält nur noch Terminalsymbole und ist daher ein Wort der Sprache.
Uneingeschränkte formale Grammatiken und Turingmaschinen sind gleichmächtig: Zu jeder von einer solchen Grammatik erzeugten Sprache gibt es eine Turingmaschine, die genau diese Sprache akzeptiert, und umgekehrt.
Die vier Grammatiktypen
Typ 0: Eine Typ-0-Grammatik ist eine unbeschränkte Grammatik und hat die Form G = (V,T,P,S). Dabei ist V = T ∪ N das Vokabular aus dem endlichen Alphabet T der Terminalsymbole und der disjunkten Menge N der Nichtterminalsymbole. S ∈ N ist das Startsymbol. Die Produktionsregeln erfüllen P ⊆ (V* \ T*) × V* = VNV × V*: Auf der linken Seite muss also mindestens ein Nichtterminalsymbol stehen. Ansonsten ist die Gestalt der Regeln uneingeschränkt.
Typ-1: Eine kontextsensitive Grammatik ist eine Typ-0-Grammatik, deren Regeln die Form αAβ → αγβ oder S → ε haben. A ist ein Nichtterminal, α, β und γ bestehen aus Terminalen und Nichtterminalen, wobei γ mindestens ein Symbol enthalten muss. Die Regel S → ε ist nur erlaubt, wenn das Startsymbol S auf keiner rechten Seite vorkommt. Die Regeln sind längenbeschränkt: Die rechte Seite ist nicht kürzer als die linke. Anders als bei Typ 2 dürfen links ganze Symbolfolgen stehen, sofern sie mindestens ein Nichtterminal enthalten.
Typ 2: Bei einer kontextfreien Grammatik hat jede Regel die Form A → γ mit A ∈ N und γ ∈ V⁺. Links steht genau ein Nichtterminalsymbol; rechts darf eine beliebige nichtleere Folge von Terminal- und Nichtterminalsymbolen stehen. Die Ausnahmeregel S → ε kann zugelassen werden, wenn S auf keiner rechten Seite vorkommt. Häufig werden kontextfreie Grammatiken allgemeiner definiert und Regeln mit leerer rechter Seite erlaubt; diese erfüllen dann nicht mehr alle Eigenschaften der ursprünglichen Typ-2-Definition.
Typ 3: Eine reguläre Grammatik ist eine Typ-2-Grammatik mit besonders eingeschränkten rechten Seiten. Erlaubt sind rechtsreguläre Regeln A → aB oder A → a sowie linksreguläre Regeln A → Ba oder A → a; A,B ∈ N und a ∈ T. Es darf entweder nur die linksreguläre oder nur die rechtsreguläre Form verwendet werden. Werden beide Formen in einer Grammatik gemischt, ist sie nicht regulär, da dadurch eine echt größere Sprachklasse entsteht. Regeln A → ε werden üblicherweise zugelassen. Linksreguläre und rechtsreguläre Grammatiken erzeugen dieselbe Sprachklasse.
Erzeugte Sprachen, Automaten und Entscheidbarkeit
Typ-0-Grammatiken erzeugen genau die rekursiv aufzählbaren, auch semi-entscheidbaren Sprachen. Eine Turingmaschine akzeptiert jedes Wort, das zur Sprache gehört. Bei einem nicht enthaltenen Wort kann sie jedoch unendlich weiterlaufen und muss keine Entscheidung liefern. Das unterscheidet rekursiv aufzählbare Sprachen von rekursiven beziehungsweise entscheidbaren Sprachen, bei denen die Turingmaschine für jedes Wort anhält.
Typ-1-Grammatiken erzeugen genau die kontextsensitiven Sprachen. Diese werden von nichtdeterministischen, linear beschränkten Turingmaschinen erkannt. Das Band ist dabei durch die Eingabelänge beschränkt: Es gibt eine konstante Zahl a, sodass höchstens a · x Felder verwendet werden, wenn x die Länge des Eingabewortes ist.
Typ-2-Grammatiken erzeugen genau die kontextfreien Sprachen. Sie entsprechen den Sprachen, die von nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge der kontextfreien Sprachen bildet die theoretische Grundlage für die Syntax der meisten Programmiersprachen. Zur Beschreibung werden auch die äquivalenten Schemata Backus-Naur-Form (BNF) und Erweiterte Backus-Naur-Form (EBNF) verwendet.
Typ-3-Grammatiken erzeugen genau die regulären Sprachen. Diese können auch durch reguläre Ausdrücke beschrieben und von endlichen Automaten erkannt werden. Sie werden häufig für Suchmuster und die lexikalische Struktur von Programmiersprachen eingesetzt.
Beim Wortproblem wird geprüft, ob ein Wort zu einer Sprache gehört. Für Typ 0 gibt es keine allgemeine Entscheidbarkeit; das Wortproblem wird nur semi-entschieden. Für Typ 1 ist das Wortproblem entscheidbar. Für Typ 2 sind Wort-, Leerheits- und Endlichkeitsproblem entscheidbar. Für Typ 3 sind zusätzlich das Äquivalenz- und das Schnittproblem entscheidbar. Als Zeitabschätzungen nennt die Übersicht für Typ 1 O(2ⁿ), für Typ 2 O(n³) und für Typ 3 O(n); Typ 0 ist unbeschränkt.
Bei den Abschlussoperationen sind Typ-0-Sprachen unter Konkatenation, Schnitt, Vereinigung und Kleeneschem Abschluss abgeschlossen. Typ-1-Sprachen zusätzlich unter Komplementbildung; Typ-2-Sprachen unter Konkatenation, Vereinigung und Kleeneschem Abschluss; Typ-3-Sprachen unter Komplement, Konkatenation, Schnitt, Vereinigung und Kleeneschem Abschluss. Dabei bedeutet ε das leere Wort, P die Menge der Produktionsregeln, V⁺ die positive Hülle und V* die Kleenesche Hülle.
Beispiele und natürliche Sprachen
Typische Beispiele für die strenge Sprachhierarchie sind L₁ = {aⁿbⁿcⁿ | n ≥ 1}, eine Sprache vom Typ 1, aber nicht vom Typ 2, und L₂ = {aⁿbⁿ | n ≥ 1}, eine Sprache vom Typ 2, aber nicht vom Typ 3. Nachweise für die Nichtzugehörigkeit zu den Klassen Typ 2 und Typ 3 werden häufig mit dem Schleifensatz geführt.
Für natürliche Sprachen ist bis heute für keine Sprache der Nachweis einer korrekten und vollständigen formalen Grammatik gelungen. Schwierigkeiten entstehen unter anderem durch das Zusammenspiel verschiedener Grammatikteile und durch Mehrdeutigkeiten auf mehreren Ebenen der Sprachbeschreibung. In der Computerlinguistik müssen solche Mehrdeutigkeiten, etwa bei maschineller Übersetzung, anhand des Kontextes aufgelöst werden.
Natürliche Sprachen sind im Allgemeinen nicht regulär, weil sie beispielsweise zentrale Einbettungen erlauben. Das Pumping-Lemma für kontextfreie Sprachen zeigt, dass die dadurch beschriebene Sprache L = {aⁿbᵐcᵐdⁿ | n,m > 0} nicht regulär ist. Außerdem reichen kontextfreie Grammatiken nicht aus, um natürliche Sprache vollständig zu beschreiben. Ein Beispiel sind kreuzende Dependenzen im Schweizerdeutschen. Die entsprechende Sprache L = {aⁿbᵐcⁿdᵐ | n,m > 0} ist nicht kontextfrei.
