Zum Inhalt springen

Chomsky-Hierarchie

Aus FLBK-Wiki
Version vom 11. November 2026, 22:03 Uhr von Flbkwikiadmin (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Chomsky-Hierarchie ordnet Grammatiken nach der Form ihrer Regeln. Daran lässt sich ablesen, welcher Automat eine Sprache erkennen kann.

Definition

Die Chomsky-Hierarchie teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 (allgemeine Grammatiken), Typ 1 (kontextsensitive Grammatiken), Typ 2 (kontextfreie Grammatiken) und Typ 3 (reguläre Grammatiken). Je höher die Nummer, desto strenger sind die Vorgaben für die Regeln.

  • Der Typ einer Grammatik ist der strengste Typ, dessen Vorgaben alle ihre Regeln erfüllen. Eine einzige Regel, die gegen die Vorgaben eines Typs verstößt, genügt, damit die Grammatik nicht zu diesem Typ gehört.
  • Der Typ einer Sprache ist der strengste Typ, für den es eine Grammatik gibt, die die Sprache erzeugt. Eine einzelne Grammatik legt den Typ der Sprache deshalb noch nicht fest: Es kann eine andere, strengere Grammatik für dieselbe Sprache geben.

Die Sprachklassen sind ineinander enthalten. Jede Sprache vom Typ 3 lässt sich auch mit einer Grammatik vom Typ 2 erzeugen, jede Sprache vom Typ 2 auch mit einer vom Typ 1 und jede Sprache vom Typ 1 auch mit einer vom Typ 0. Die Umkehrungen gelten nicht.

[math]\displaystyle{ \text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0} }[/math]

Diese Einschlüsse gelten für die Sprachklassen, nicht für jede einzelne Grammatik. Die kontextfreie Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math] zum Beispiel erfüllt die Vorgaben von Typ 1 nicht: Die rechte Seite der Regel [math]\displaystyle{ S \to \varepsilon }[/math] ist kürzer als die linke, und die Ausnahme für das leere Wort (siehe Sprachklassen und Automatenmodelle) greift nicht, weil [math]\displaystyle{ S }[/math] auch auf einer rechten Regelseite vorkommt. Zu ihr gibt es aber eine gleichwertige Grammatik, die diese Vorgaben erfüllt.

Sprachklassen und Automatenmodelle

Die Sprachklassen der Chomsky-Hierarchie sind ineinander enthalten

Die Tabelle nennt zu jedem Typ die Sprachklasse, die erlaubte Regelform und den Automaten, der genau diese Sprachen erkennt. Dabei sind [math]\displaystyle{ A }[/math] und [math]\displaystyle{ B }[/math] Nichtterminale, [math]\displaystyle{ a }[/math] ist ein Terminal und [math]\displaystyle{ \beta }[/math] ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen.

Typ Sprachklasse Regelform Automatenmodell
0 rekursiv aufzählbar beliebig, links mindestens ein Nichtterminal Turingmaschine
1 kontextsensitiv rechte Seite mindestens so lang wie die linke linear beschränkter Automat
2 kontextfrei [math]\displaystyle{ A \to \beta }[/math] Kellerautomat
3 regulär [math]\displaystyle{ A \to aB }[/math] und [math]\displaystyle{ A \to a }[/math] endlicher Automat

Zu den Regelformen gehören diese Ergänzungen:

  • Leeres Wort: Bei Typ 1 und bei regulären Grammatiken ist die Regel [math]\displaystyle{ S \to \varepsilon }[/math] als Ausnahme erlaubt, wenn das Startsymbol [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt. So kann auch das leere Wort zur Sprache gehören. Bei Typ 2 und bei rechtslinearen Grammatiken darf jedes Nichtterminal eine Regel [math]\displaystyle{ A \to \varepsilon }[/math] haben.
  • Typ 0: Rekursiv aufzählbar heißt eine Sprache, wenn ein Verfahren ihre Wörter nacheinander aufzählen kann. Eine Turingmaschine akzeptiert dann jedes Wort der Sprache. Bei einer Eingabe, die nicht zur Sprache gehört, hält sie aber möglicherweise nie an.
  • Typ 1: Kontextsensitiv bedeutet, dass eine Regel ein Nichtterminal abhängig von seinen Nachbarzeichen ersetzen darf, dem Kontext. Auf der linken Seite stehen dann neben dem Nichtterminal weitere Zeichen. Die rechte Seite darf nicht kürzer sein als die linke. Einzige Ausnahme ist die Regel [math]\displaystyle{ S \to \varepsilon }[/math], wenn [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt.
  • Typ 2: Links steht genau ein Nichtterminal. Es wird unabhängig von seinen Nachbarzeichen ersetzt, daher der Name kontextfrei.
  • Typ 3: Auch rechtslineare Grammatiken erzeugen genau die regulären Sprachen und werden deshalb ebenfalls zu Typ 3 gezählt. Jede endliche Sprache ist regulär: Für jedes ihrer Wörter [math]\displaystyle{ w }[/math] genügt eine Regel [math]\displaystyle{ S \to w }[/math], und eine Grammatik aus solchen Regeln ist rechtslinear.

Die Automatenmodelle unterscheiden sich in ihrem Speicher:

Automatenmodell Speicher Zugriff auf den Speicher
endlicher Automat nur der aktuelle Zustand kein zusätzlicher Speicher
Kellerautomat unbegrenzter Keller nur auf das oberste Zeichen
linear beschränkter Automat Band, so lang wie die Eingabe lesen und schreiben an jeder Stelle des Bandes
Turingmaschine unbegrenztes Band lesen und schreiben an jeder Stelle des Bandes

Für alle kontextfreien Sprachen braucht es nichtdeterministische Kellerautomaten. Deterministische Kellerautomaten erkennen nur einen Teil der kontextfreien Sprachen, darunter alle regulären.

Beispiele

Typ einzelner Regeln bestimmen

Für vier Regeln wird der strengste Typ gesucht, dessen Vorgaben die Regel erfüllt. Großbuchstaben sind Nichtterminale, Kleinbuchstaben sind Terminale.

Regel strengster Typ Begründung
[math]\displaystyle{ B \to bC }[/math] 3 Links steht ein Nichtterminal, rechts ein Terminal und dahinter ein Nichtterminal.
[math]\displaystyle{ S \to aSb }[/math] 2 Links steht ein Nichtterminal. Rechts steht das Nichtterminal in der Mitte, das erlaubt Typ 3 nicht.
[math]\displaystyle{ AB \to BA }[/math] 1 Links stehen zwei Zeichen, das erlaubt Typ 2 nicht. Die rechte Seite ist so lang wie die linke.
[math]\displaystyle{ aAb \to ab }[/math] 0 Die rechte Seite ist kürzer als die linke, das erlaubt Typ 1 nicht.

Typ einer Grammatik bestimmen

Gegeben sind drei Grammatiken über den Terminalen [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math]:

  • Grammatik 1 mit den Regeln [math]\displaystyle{ S \to KS \mid KE }[/math]: Beide Regeln haben links ein Nichtterminal, und rechts steht das Nichtterminal höchstens am Ende. Die Grammatik ist rechtslinear und gehört zum Typ 3.
  • Grammatik 2 mit den Regeln [math]\displaystyle{ S \to KSE \mid E }[/math]: Beide Regeln haben links genau ein Nichtterminal, die Grammatik erfüllt also die Vorgaben von Typ 2. In der Regel [math]\displaystyle{ S \to KSE }[/math] steht das Nichtterminal aber in der Mitte. Diese eine Regel verstößt gegen die Vorgaben von Typ 3. Die Grammatik gehört zum Typ 2.
  • Grammatik 3 mit den Regeln [math]\displaystyle{ S \to KS \mid \varepsilon }[/math]: Das Nichtterminal steht höchstens am Ende, die Grammatik ist rechtslinear und gehört zum Typ 3. Sie erfüllt aber nicht die engere Form der regulären Grammatik, denn dort ist [math]\displaystyle{ S \to \varepsilon }[/math] nur erlaubt, wenn [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt. Wie daraus eine reguläre Grammatik wird, beschreibt der Abschnitt Rechtslineare Grammatik.

Sprachen einordnen

Jede Sprache wird dem strengsten Typ zugeordnet, für den es eine Grammatik gibt, die sie erzeugt.

  • Die Wörter des Kaffeeautomaten bilden die endliche Sprache [math]\displaystyle{ L = \{KKKK; EE; EKK; KEK; KKE\} }[/math]. Ein endlicher Automat erkennt sie, und eine Grammatik mit nur den Regelformen [math]\displaystyle{ A \to aB }[/math] und [math]\displaystyle{ A \to a }[/math] erzeugt sie, siehe Grammatik zum Kaffeeautomaten angeben. Die Sprache ist regulär: Typ 3.
  • Korrekt geklammerte Ausdrücke erzeugt die Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]. Ihre Regeln haben links genau ein Nichtterminal, die Sprache ist also kontextfrei, siehe Kontextfreie Grammatik. Ein endlicher Automat kann beliebig tiefe Klammerung nicht mitzählen, die Sprache ist deshalb nicht regulär, siehe Grenzen regulärer Sprachen. Sie gehört zu Typ 2, nicht zu Typ 3.
  • Die Sprache [math]\displaystyle{ \{a^n b^n c^n \mid n \geq 1\} }[/math] verlangt gleich viele [math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math] und [math]\displaystyle{ c }[/math] in dieser Reihenfolge. Die Schreibweise mit Exponenten ist eine Wortpotenz. Die Sprache ist kontextsensitiv, aber nicht kontextfrei: Typ 1, nicht Typ 2. Anschaulich: Ein Kellerautomat kann die Anzahl der [math]\displaystyle{ a }[/math] im Keller ablegen und beim Lesen der [math]\displaystyle{ b }[/math] wieder abbauen. Danach ist der Keller abgebaut, und für den Vergleich mit den [math]\displaystyle{ c }[/math] fehlt die Anzahl.
  • Die Sprache [math]\displaystyle{ \{K^n E \mid n \geq 1\} }[/math] lässt sich mit den Regeln [math]\displaystyle{ S \to AE }[/math] und [math]\displaystyle{ A \to KA \mid K }[/math] erzeugen. Diese Grammatik ist nicht rechtslinear. Trotzdem ist die Sprache regulär, denn die rechtslineare Grammatik [math]\displaystyle{ S \to KS \mid KE }[/math] erzeugt sie ebenfalls, siehe Grammatik in eine rechtslineare Grammatik umformen. Die Sprache gehört zu Typ 3: Maßgeblich ist die strengste Grammatik, die es für die Sprache gibt.