Chomsky-Hierarchie

Wenn ein Compiler deinen Programmcode liest, fragt er nicht: "Klingt das gut?" Er prüft, ob die Zeichenfolge zu einer genau festgelegten Sprache gehört.

Die Chomsky-Hierarchie hilft dir, solche Sprachen nach ihrer Regelstärke zu ordnen. Danach kannst du einschätzen, ob ein endlicher Automat reicht, ob ein Stapel gebraucht wird oder ob das Problem viel mächtiger ist.

Deine Lernziele

• Ich kann erklären, was eine formale Sprache und eine Grammatik sind.
• Ich kann Terminale, Nichtterminale, Startsymbol und Produktionsregeln unterscheiden.
• Ich kann die vier Typen der Chomsky-Hierarchie in die richtige Reihenfolge bringen.
• Ich kann typische Regelbeschränkungen für Typ 0, Typ 1, Typ 2 und Typ 3 erkennen.
• Ich kann einfache Beispiele passenden Sprachklassen und Automatenmodellen zuordnen.

Warum die Hierarchie gebraucht wird

Viele Informatikprobleme wirken erst einmal gleich: Ein Eingabewort kommt rein, und das System soll entscheiden, ob es passt. Bei einer E-Mail-Adresse, einer Klammerung oder einem Programmausdruck steckt aber unterschiedlich viel Struktur dahinter.

Definition

Formale Sprache

Eine formale Sprache ist eine Menge von Wörtern über einem festen Alphabet. Ein Wort ist dabei eine endliche Folge von Zeichen aus diesem Alphabet.

Nimm das Alphabet \(\Sigma=\{a,b\}\). Dann sind a, bb und abba Wörter über diesem Alphabet. Die Menge aller Wörter, die genau zwei Zeichen lang sind, ist zum Beispiel \(\{aa,ab,ba,bb\}\).

Beispiel

Wir betrachten die Sprache aller Wörter über \(\{a,b\}\), die mit a beginnen und mit b enden.

1. ab gehört dazu, weil das erste Zeichen a und das letzte Zeichen b ist.
2. aaab gehört dazu, auch wenn in der Mitte weitere a stehen.
3. baab gehört nicht dazu, weil es mit b beginnt.
4. aaba gehört nicht dazu, weil es mit a endet.

Diese Sprache kann unendlich viele Wörter enthalten, obwohl ihre Beschreibung kurz ist.

Merke

Eine formale Sprache ist keine Programmiersprache im Alltagssinn, sondern eine exakt beschriebene Menge von Zeichenketten.

Grammatiken: Regeln erzeugen Wörter

Eine unendliche Sprache lässt sich nicht sinnvoll durch Aufzählen lernen. Darum beschreibt man oft Regeln, mit denen gültige Wörter Schritt für Schritt entstehen.

Definition

Grammatik

Eine Grammatik ist ein Erzeugungssystem \(G=(N,T,P,S)\). \(N\) ist die Menge der Nichtterminale, \(T\) die Menge der Terminale, \(P\) die Menge der Produktionsregeln und \(S\) das Startsymbol.

Terminale sind die Zeichen, die am Ende wirklich im Wort stehen. Nichtterminale sind Platzhalter, die noch ersetzt werden müssen. Eine Produktionsregel sagt, welche Zeichenfolge durch welche andere Zeichenfolge ersetzt werden darf.

Beispiel

Die Sprache \(\{a^n b^n \mid n \ge 0\}\) enthält \(\varepsilon\), ab, aabb, aaabbb und so weiter. Es stehen immer gleich viele a vorne wie b hinten.

Eine passende Grammatik nutzt das Nichtterminal \(S\):

• \(S \to aSb\)
• \(S \to \varepsilon\)

Ableitung für aabb:

1. \(S\)
2. \(aSb\)
3. \(aaSbb\)
4. \(aabb\)

Die erste Regel legt gleichzeitig ein neues a vorne und ein neues b hinten an. Die zweite Regel beendet die Ableitung.

Gut zu wissen

Das Zeichen \(\varepsilon\) steht für das leere Wort. Es fügt also kein sichtbares Zeichen hinzu, sondern beendet in vielen Grammatiken eine Rekursion.

Die vier Stufen der Chomsky-Hierarchie

Die Chomsky-Hierarchie ordnet Grammatiken danach, wie stark ihre Regeln eingeschränkt sind. Je stärker die Einschränkung, desto einfacher ist die Sprachklasse.

Definition

Chomsky-Hierarchie

Die Chomsky-Hierarchie ist die Einteilung formaler Grammatiken und Sprachen in Typ 0, Typ 1, Typ 2 und Typ 3. Dabei gilt: Typ 3 ist echt in Typ 2 enthalten, Typ 2 echt in Typ 1 und Typ 1 echt in Typ 0.

Das bedeutet:

Typ 0 ist am mächtigsten, aber am wenigsten eingeschränkt. Typ 3 ist am einfachsten, dafür besonders gut automatisch zu prüfen. "Echt enthalten" heißt: In jeder größeren Klasse gibt es Sprachen, die in der kleineren Klasse noch nicht möglich sind.

Beispiel

Stell dir vier Werkzeugkästen vor:

1. Typ 3 hat nur einen kleinen Schraubendreher, reicht aber für einfache Muster wie "beliebig viele a".
2. Typ 2 hat zusätzlich einen Stapel, damit verschachtelte Strukturen wie Klammern gehen.
3. Typ 1 kann mehrere Zähler in Beziehung setzen, etwa gleich viele a, b und c.
4. Typ 0 darf fast beliebige Ersetzungen nutzen und kommt dadurch in die Nähe allgemeiner Berechnung.

Die Werkzeugkästen liegen ineinander: Wer Typ 0 kann, kann auch die einfacheren Klassen erzeugen.

Merke

Kleine Typnummer bedeutet mehr Ausdruckskraft. Größere Typnummer bedeutet strengere Regeln.

Typ 3 bis Typ 0 im Vergleich

In Prüfungen musst du oft eine Regel oder Sprache einordnen. Am besten gehst du von der strengsten Klasse aus und fragst: Erfüllt sie deren Form?

Definition

Typ 3

Eine Grammatik ist regulär oder vom Typ 3, wenn ihre Regeln zum Beispiel rechtslinear sind: \(A \to aB\), \(A \to a\) oder \(A \to \varepsilon\). Links steht genau ein Nichtterminal. Eine Typ-3-Grammatik bleibt dabei in einer Richtung: rechtslinear oder linkslinear, aber nicht gemischt.

Reguläre Sprachen passen zu endlichen Automaten. Ein endlicher Automat merkt sich nur endlich viele Zustände, aber keinen unbeschränkten Zähler und keinen Stapel.

Beispiel

Die Sprache \(\{a^n \mid n \ge 0\}\) ist regulär.

Grammatik:

• \(S \to aS\)
• \(S \to \varepsilon\)

Ableitung für aaa:

\(S \Rightarrow aS \Rightarrow aaS \Rightarrow aaaS \Rightarrow aaa\)

Es muss nichts verglichen werden. Die Grammatik hängt einfach beliebig viele a an.

Definition

Typ 2

Eine Grammatik ist kontextfrei oder vom Typ 2, wenn links in jeder Regel genau ein Nichtterminal steht. Rechts darf eine beliebige endliche Folge aus Terminalen und Nichtterminalen stehen.

Kontextfreie Sprachen passen zu nichtdeterministischen Kellerautomaten. Ein Kellerautomat hat einen Stapel und kann damit etwa verschachtelte Klammern oder gleiche Anzahlen in einer Richtung verfolgen.

Beispiel

Die Sprache \(\{a^n b^n \mid n \ge 0\}\) ist kontextfrei.

Die Regel \(S \to aSb\) erzeugt immer ein passendes Paar. Das mittlere \(S\) merkt sich indirekt, dass später noch beendet werden muss. Diese Paarbindung schafft ein endlicher Automat nicht für beliebig große \(n\).

Definition

Typ 1

Eine Grammatik ist kontextsensitiv oder vom Typ 1, wenn sie im Kern keine Regel hat, die eine Satzform kürzer macht: Für jede Regel \(\alpha \to \beta\) gilt \(|\alpha| \le |\beta|\). Die Sonderregel \(S \to \varepsilon\) ist nur unter einer Zusatzbedingung erlaubt.

Gut zu wissen

Bei \(\varepsilon\)-Regeln gibt es je nach Lehrbuch kleine Konventionsunterschiede. Wichtig für dich: \(S \to aSb\) und \(S \to \varepsilon\) ist als kontextfreie Grammatik gültig, erfüllt aber nicht automatisch die strengere Typ-1-Sonderregel, weil \(S\) rechts in \(aSb\) vorkommt.

Kontextsensitive Sprachen passen zu nichtdeterministischen linear beschränkten Automaten. Sie können stärkere Abhängigkeiten beschreiben als kontextfreie Sprachen.

Beispiel

Die Sprache \(\{a^n b^n c^n \mid n \ge 1\}\) ist ein typisches Beispiel für Typ 1 und ist nach den üblichen Beweismethoden, etwa dem Pumping-Lemma für kontextfreie Sprachen, nicht kontextfrei.

Als Merkhilfe: Bei aaabbbccc müssen drei Gruppen dieselbe Länge haben. Ein einzelner Stapel kann gut die a gegen die b abgleichen, aber danach müsste er dieselbe Anzahl noch einmal für die c kennen. Das ist Intuition, kein vollständiger Beweis.

Definition

Typ 0

Eine Grammatik ist unbeschränkt oder vom Typ 0, wenn links in jeder Regel mindestens ein Nichtterminal vorkommt. Die Regeln dürfen sonst sehr frei sein.

Typ-0-Sprachen entsprechen den Sprachen, die Turingmaschinen akzeptieren können. Das ist sehr mächtig, aber nicht automatisch entscheidbar.

Merke

Typ 3: endlicher Automat. Typ 2: nichtdeterministischer Kellerautomat. Typ 1: nichtdeterministischer linear beschränkter Automat. Typ 0: Turingmaschine.

Prüfungsmodus

Bei Aufgaben zur Chomsky-Hierarchie sind zwei Fehler besonders häufig: Man verwechselt die Richtung der Hierarchie, oder man klassifiziert eine Grammatik statt der erzeugten Sprache.

Gut zu wissen

Eine nicht-regulär aussehende Grammatik kann trotzdem eine reguläre Sprache erzeugen. Die Grammatik selbst und die Sprache, die sie erzeugt, sind nicht immer gleich streng einzuordnen.

Beispiel

Aufgabe: Ordne die Regelmenge ein.

• \(S \to aS\)
• \(S \to b\)

Links steht immer genau ein Nichtterminal. Rechts steht entweder ein Terminal gefolgt von einem Nichtterminal oder nur ein Terminal. Also ist diese Grammatik regulär, damit auch kontextfrei, kontextsensitiv und Typ 0.

Die erzeugte Sprache ist \(\{a^n b \mid n \ge 0\}\), also b, ab, aab, aaab und so weiter.

Beispiel

Aufgabe: Finde den Fehler in der Begründung.

"Die Sprache \(\{a^n b^n \mid n \ge 0\}\) ist nicht regulär. Also ist sie auch nicht kontextfrei."

Der zweite Satz ist falsch. Nicht regulär bedeutet nur: Sie liegt nicht in Typ 3. Sie kann trotzdem in Typ 2 liegen, und genau das tut sie.

Alles auf einen Blick

Abschluss-Check

Jetzt prüfst du nicht mehr nur Begriffe, sondern wendest die Hierarchie auf neue Situationen an.

Zusammenfassung

Die Chomsky-Hierarchie sortiert formale Sprachen nach der Form ihrer Grammatiken. Vorher brauchst du die Grundidee: Eine Sprache ist eine Menge von Wörtern, und eine Grammatik erzeugt solche Wörter mit Terminalen, Nichtterminalen, Startsymbol und Produktionsregeln.

Typ 3 ist regulär und passt zu endlichen Automaten. Typ 2 ist kontextfrei und passt zu nichtdeterministischen Kellerautomaten. Typ 1 ist kontextsensitiv und passt zu nichtdeterministischen linear beschränkten Automaten. Typ 0 ist unbeschränkt und passt zur Akzeptanz durch Turingmaschinen.

Prüfe in Aufgaben immer die Richtung: Regulär liegt innerhalb von kontextfrei, kontextfrei innerhalb von kontextsensitiv, kontextsensitiv innerhalb von Typ 0. Wenn eine Sprache nicht regulär ist, ist sie dadurch nicht automatisch außerhalb der größeren Klassen.