Chomsky-Hierarchie

Aus Zweites Gehirn, dem persönlichen Wiki
Chomsky-Hierarchie
TypKonzept
QuellenQuelle - Automatentheorie Zusammenfassung
Erstellt2026-09-24
Aktualisiert2026-09-24
Tagstheoretische-informatik, formale-sprachen, überblick

Einteilung der formalen Sprachen in vier ineinander geschachtelte Klassen (Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0), jeweils mit passender Grammatikform und passendem Automatenmodell.

Übersicht

Typ Sprachklasse Grammatik (Regelform) Automat Wortproblem
3 regulär (REG) rechts- oder linkslinear: A → aB, A → a Endlicher Automat entscheidbar, linear
2 kontextfrei (kfS) A → beliebiges Wort Kellerautomat (PDA) entscheidbar (z.B. CYK, O(n³))
1 kontextsensitiv (ksS) α → β mit |α| ≤ |β| (monoton) linear beschränkter Automat (LBA) entscheidbar
0 rekursiv aufzählbar (RE) beliebig, links mindestens ein Nichtterminal Turingmaschine nur semi-entscheidbar

Es gilt Typ 3 ⊊ Typ 2 ⊊ Typ 1 ⊊ Typ 0 ⊊ 2^(Σ*). Trennende Beispiele: aⁿbⁿ (kontextfrei, nicht regulär), aⁿbⁿcⁿ (kontextsensitiv, nicht kontextfrei) (Quelle - Automatentheorie Zusammenfassung).

Übersichtstabellen der Quelle (S. 39–40)

Äquivalente Beschreibungskonzepte:

Sprachklasse Konzepte
Typ 3 DFA, NFA, ε-FA, GFA, reguläre Ausdrücke, rechts- und linkslineare (auch verallgemeinerte) Grammatiken
deterministisch kontextfrei DPDA, LR(k)-Grammatiken
Typ 2 kontextfreie Grammatiken, Kellerautomaten (PDA)
Typ 1 kontextsensitive Grammatiken, LBA
Typ 0 Typ-0-Grammatiken, nichtdeterministische und deterministische Turingautomaten

Zeitaufwand für das Wortproblem: Typ 3 O(n) (mit DFA) · DPDA O(n) · Typ 2 O(n³) (Grammatik in CNF) · Typ 1 2^O(n) · Typ 0 unlösbar.

Abschlusseigenschaften (× = abgeschlossen):

Klasse ∩ ∪ Komplement Konkatenation *
Typ 3 × × × × ×
DPDA – – × – –
Typ 2 – × – × ×
Typ 1 × × × × ×
Typ 0 × × – × ×

Entscheidbarkeit (× = entscheidbar):

Klasse Wortproblem Leerheit Schnitt Äquivalenz
Typ 3 × × × ×
DPDA × × – ?
Typ 2 × × – –
Typ 1 × – – –
Typ 0 – – – –
Fehler und veraltete Angabe in der Quelle
  • Auf S. 40 sind die Überschriften verschoben: Unter „Abschlusseigenschaften“ steht die Komplexitätstabelle, unter „Entscheidbarkeit“ die Abschlusstabelle, unter „Wortproblem“ die Entscheidbarkeitstabelle. Oben sind die Tabellen richtig zugeordnet.
  • Das „?“ bei der Äquivalenz für DPDA war 2002 schon überholt. Sénizergues hat 1997 bewiesen, dass die Äquivalenz deterministischer Kellerautomaten entscheidbar ist (Gödel-Preis 2002). (Einordnung Claude)

Kontextsensitive Sprachen (Typ 1)

  • Die linke Regelseite darf ein Wort aus Terminalen und Nichtterminalen sein, sofern es mindestens ein Nichtterminal enthält.
  • Monotonie: Die rechte Seite ist nie kürzer als die linke, abgeleitete Wörter wachsen also nie. Daraus folgt: Für Wörter der Länge ≤ n gibt es eine maximale Schrittzahl, und deshalb ist das Wortproblem entscheidbar.
  • Beispiel G₁ (S. 32) für aⁿbⁿcⁿ: S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc. Ableitung von a³b³c³: S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaBCBCBC. Dann sortiert CB → BC die B's vor die C's (aaaBBBCCC), danach werden sie von links nach rechts in b's und c's umgewandelt → aaabbbccc.
  • Beispiel G₂ (S. 33) für aᵐbⁿcᵐdⁿ (m, n ≥ 1): S → T₁T₂, T₁ → aT₁C | aC, T₂ → bT₂d | bd erzeugt aᵐCᵐbⁿdⁿ. Die Regeln Cb → bC, Cd → cd, Cc → cc vertauschen und verwandeln die C's. Beispielableitung bis a²b³c²d³.
Ungenauigkeit in der Quelle

Die Quelle sagt, kontextsensitive Sprachen könnten das leere Wort nie enthalten (weil monotone Regeln es nicht erzeugen). Das gilt nur für die strenge Definition. Üblich ist die Sonderregel S → ε, sofern S auf keiner rechten Seite vorkommt. So wird jede kontextfreie Sprache auch kontextsensitiv, auch eine mit ε. Ausserdem steht auf S. 32 „kfS“, gemeint ist „ksS“ (Quelle - Automatentheorie Zusammenfassung).

Linear beschränkter Automat (LBA)

Eine nichtdeterministische Turingmaschine, die nur den Bandbereich des Eingabeworts benutzen darf. LBA = Typ 1.

Typ 0 und darüber hinaus

  • Typ-0-Grammatiken heben die Monotonie auf, Wörter dürfen beim Ableiten schrumpfen. Sie erzeugen genau die von Turingmaschinen akzeptierten Sprachen (rekursiv aufzählbar = semi-entscheidbar).
  • Abzählbarkeitsargument: Typ-0-Grammatiken gibt es nur abzählbar viele, Sprachen dagegen überabzählbar viele. Also gibt es Sprachen, die gar keine Grammatik erzeugt → Berechenbarkeit.
  • Abzählbar sind z.B. die geraden und die rationalen Zahlen. Überabzählbar sind die reellen Zahlen und die Menge aller Sprachen 2^(Σ*).

Muster: Determinismus

Modell Nichtdeterminismus stärker?
Endlicher Automat nein (Potenzmengenkonstruktion)
Kellerautomat ja (DPDA ⊊ PDA)
LBA offen (LBA-Problem)
Turingmaschine nein (aber exponentieller Zeitaufwand → Komplexitätstheorie)

Verwandt

Links auf diese Seite

Kategorien: theoretische-informatik | formale-sprachen | überblick