Chomsky-Hierarchie

Die Chomsky-Hierarchie wurde 1956 vom Linguisten Noam Chomsky vorgeschlagen, um formale Sprachen nach der Mächtigkeit ihrer Grammatiken zu klassifizieren. Sie umfasst vier Typen, die echt ineinander liegen: \( \text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0} \). Jeder Typ entspricht einem bestimmten Berechnungsmodell. Die Hierarchie ist die Brücke zwischen Grammatiken, Sprachen und Automaten.

Typ 3 – Reguläre Sprachen:

• Erkannt durch endliche Automaten (DEA/NEA)
• Erzeugt durch reguläre Grammatiken und reguläre Ausdrücke
• Produktionsregeln der Form \( A \rightarrow aB \) oder \( A \rightarrow a \)
• Beispiel: \( L = \{a^n b \mid n \geq 0\} = a^* b \)

Typ 2 – Kontextfreie Sprachen:

• Erkannt durch Kellerautomaten (Pushdown-Automaten)
• Erzeugt durch kontextfreie Grammatiken
• Produktionsregeln der Form \( A \rightarrow \alpha \), Linke Seite ist genau ein Nichtterminal
• Beispiel: \( L = \{a^n b^n \mid n \geq 1\} \) – gleich viele a wie b

Typ 1 – Kontextsensitive Sprachen:

• Erkannt durch linear beschränkte Automaten
• Produktionsregeln \( \alpha A \beta \rightarrow \alpha \gamma \beta \), das Nichtterminal A wird im Kontext \( \alpha \beta \) ersetzt
• Beispiel: \( L = \{a^n b^n c^n \mid n \geq 1\} \)

Typ 0 – Rekursiv aufzählbare Sprachen:

• Erkannt durch Turingmaschinen
• Keine Einschränkungen an die Grammatikregeln
• Beispiel: jede berechenbare Sprache, etwa die Menge aller gültigen Java-Programme

Hierarchie: Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0

Jeder Stufe der Hierarchie entspricht ein Berechnungsmodell mit einer bestimmten „Speicherfähigkeit“:

• Typ 3 – endlicher Automat: kein zusätzlicher Speicher.
• Typ 2 – Kellerautomat: ein Stack als Hilfsspeicher.
• Typ 1 – linear beschränkter Automat: Bandlänge proportional zur Eingabe.
• Typ 0 – Turingmaschine: unendliches Band, volle Berechnungsmächtigkeit.

Die zunehmende Speicherstärke spiegelt die wachsende Sprachklasse wider.

Die Inklusionen sind echt: \( a^n b^n \) ist kontextfrei, aber nicht regulär – das lässt sich mit dem Pumping-Lemma für reguläre Sprachen beweisen. Analog ist \( a^n b^n c^n \) kontextsensitiv, aber nicht kontextfrei. Das zeigt: jede zusätzliche Speicherform erweitert die ausdrückbaren Sprachen.

Die Hierarchie erklärt, warum Programmiersprachen typischerweise kontextfrei definiert werden (BNF-Grammatik) und mit Kellerautomaten geparst werden (z. B. LL(1) oder LR(1)). Lexer arbeiten mit regulären Sprachen, da Token durch endliche Automaten erkannt werden. Natürliche Sprachen sind dagegen mindestens kontextsensitiv.

Falsche Zuordnung der Typen (Typ 0 ist die größte Klasse, nicht die kleinste), Verwechslung von Sprache und Grammatik, unsaubere Produktionsregeln (z. B. eine kontextfreie Regel mit zwei Nichtterminalen links).

Zusammenfassung: Die Chomsky-Hierarchie ordnet formale Sprachen vier Typen zu, von den regulären (Typ 3) bis zu den rekursiv aufzählbaren (Typ 0). Jedem Typ entspricht ein Berechnungsmodell mit zunehmender Speicherstärke.

Abitur-Tipp: Lerne für jeden Typ ein kanonisches Beispiel auswendig: \( a^* b \) (Typ 3), \( a^n b^n \) (Typ 2), \( a^n b^n c^n \) (Typ 1), Halteproblem-Sprache (Typ 0).