Chomsky-Hierarchie — Theo. Informatik

Vier ineinander geschachtelte Klassen formaler Sprachen — von universeller Berechenbarkeit hinunter zu endlichen Automaten.

Klausur-Relevanz · sehr hoch · Lesen UND Rechnen

TL;DR

Die Hierarchie ordnet Grammatiken in vier ineinandergeschachtelte Klassen: $\text{Typ 0} \supset \text{Typ 1} \supset \text{Typ 2} \supset \text{Typ 3}$.
Kriterium ist ausschließlich die Form der Produktionen — nicht die erzeugte Sprache selbst.
Jeder Typ korrespondiert mit einem Automatenmodell: Turingmaschine, linear beschränkter Automat, Kellerautomat, endlicher Automat.
Bei der Einordnung gewinnt die restriktivste passende Klasse — also die mit der höchsten Typ-Zahl, die alle Produktionen noch erfüllen.
Falle: eine Grammatik, deren Sprache regulär ist, muss selbst nicht Typ 3 sein — die Form der Regeln entscheidet, nicht die Sprache.
Neu: Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben mit KaTeX-Formeln und schrittweisen Lösungen im unteren Abschnitt.

1 · Definitionen & Formalismen

Grammatik $G = (V, \Sigma, P, S)$

Eine formale Grammatik besteht aus einer endlichen Menge $V$ von Variablen (Nichtterminalen), einer endlichen Menge $\Sigma$ von Terminalen mit $V \cap \Sigma = \emptyset$, einer endlichen Menge $P \subseteq (V \cup \Sigma)^+ \times (V \cup \Sigma)^*$ von Produktionen und einem Startsymbol $S \in V$. Die von $G$ erzeugte Sprache ist:

$$L(G) = \{\, w \in \Sigma^* \mid S \Rightarrow^* w \,\}$$

Typ 0 · Rekursiv aufzählbar (Phrasenstrukturgrammatik)

Produktionen haben die Form $\alpha \to \beta$ mit $\alpha \in (V \cup \Sigma)^* \cdot V \cdot (V \cup \Sigma)^*$ und $\beta \in (V \cup \Sigma)^*$. Die linke Seite muss mindestens eine Variable enthalten, sonst keine Einschränkung. Automatenmodell: Turingmaschine. Beispielsprache: jede semi-entscheidbare Sprache, z. B. das Halteproblem als Menge kodierter Instanzen.

Typ 1 · Kontextsensitiv (längenmonoton)

Jede Produktion hat die Form $\alpha A \beta \to \alpha \gamma \beta$ mit $A \in V$, $\alpha, \beta \in (V \cup \Sigma)^*$ und $\gamma \in (V \cup \Sigma)^+$. Äquivalent gilt die längenmonotone Bedingung:

$$|\alpha A \beta| \le |\alpha \gamma \beta| \quad\Longleftrightarrow\quad |\text{linke Seite}| \le |\text{rechte Seite}|$$

Ausnahme: $S \to \varepsilon$ ist erlaubt, falls $S$ auf keiner rechten Seite vorkommt. Automatenmodell: linear beschränkter Automat (LBA). Beispielsprache: $L = \{\, a^n b^n c^n \mid n \ge 1 \,\}$.

Typ 2 · Kontextfrei

Jede Produktion hat die Form $A \to \beta$ mit $A \in V$ und $\beta \in (V \cup \Sigma)^*$. Die linke Seite besteht aus genau einer Variable, ohne Kontext. Automatenmodell: nichtdeterministischer Kellerautomat (PDA). Beispielsprache: $L = \{\, a^n b^n \mid n \ge 0 \,\}$ oder korrekt geklammerte Ausdrücke.

Typ 3 · Regulär (rechtslinear)

Jede Produktion hat die Form $A \to aB$, $A \to a$ oder $A \to \varepsilon$ mit $A, B \in V$ und $a \in \Sigma$. Auf der rechten Seite steht höchstens ein Terminal, gefolgt von höchstens einer Variable — nie umgekehrt, nie mehrere Terminale hintereinander in einer Regel. Automatenmodell: endlicher Automat (DFA/NFA). Beispielsprache: $L = a^* b^*$ oder alle durch 3 teilbaren Binärzahlen.

2 · Kernkonzepte · Vorgehen zur Einordnung

Bei einer gegebenen Grammatik ist die Frage der Klausur meistens: welchen Typ hat sie? Vorgehen in vier Schritten:

Alle Produktionen einzeln prüfen. Für jede Regel notiere ich, welche Typen sie noch erlaubt. Eine Grammatik ist so restriktiv, wie es ihre restriktivste Produktion zulässt.
Von unten nach oben lockern. Ich starte bei Typ 3. Verletzt eine Regel die rechtslineare Form? Dann höchstens Typ 2. Verletzt sie das kontextfreie Format (mehr als eine Variable links, Kontext um $A$)? Dann höchstens Typ 1. Verletzt sie die Längenmonotonie (rechte Seite kürzer als linke)? Dann nur noch Typ 0.
Höchstmöglichen Typ wählen. Die passende Antwort ist die größte Zahl, die alle Regeln zulassen — also die restriktivste Klasse. Typ 3 ist restriktiver als Typ 2, obwohl die Zahl größer ist.
Nicht auf die Sprache achten. Die Klassifikation bezieht sich auf die Grammatik, nicht auf die erzeugte Sprache. Eine Typ-0-Grammatik kann eine reguläre Sprache erzeugen — sie bleibt trotzdem Typ 0.

3 · Beispiel durchgerechnet

Aufgabe · Klassifiziere die folgende Grammatik

Gegeben ist $G = (V, \Sigma, P, S)$ mit $V = \{S, A, B\}$, $\Sigma = \{a, b, c\}$ und Produktionen:

P1:  S → aSBC
P2:  S → aBC
P3:  CB → BC
P4:  aB → ab
P5:  bB → bb
P6:  bC → bc
P7:  cC → cc

Schritt 1 · Regeln einzeln prüfen

$S \to aSBC$: linke Seite eine Variable, rechte Seite länger — kontextfrei-konform, aber rechte Seite ist nicht rechtslinear (mehrere Variablen nach dem Terminal). Also höchstens Typ 2 wegen dieser Regel isoliert.
$CB \to BC$: linke Seite hat zwei Variablen. Damit fällt Typ 2 raus. Länge links $= 2$, Länge rechts $= 2$, also längenmonoton — Typ 1 möglich, sofern kontextsensitive Form $\alpha A \beta \to \alpha \gamma \beta$ passt. Hier: $C \cdot B \to B \cdot C$. Man muss diese Regel in das kontextsensitive Schema pressen. Das gelingt nicht direkt (weder $C$ noch $B$ bleibt als Kontext stehen), sondern nur über eine Ersetzung — daher ist sie im engeren Sinn nicht kontextsensitiv nach der Definition $\alpha A \beta \to \alpha \gamma \beta$. Die weiter gefasste Definition Typ 1 lässt jedoch beliebige längenmonotone Regeln zu und ist äquivalent zur kontextsensitiven Form (Kuroda/Penttonen-Normalform). Wir bleiben bei Typ 1.
$aB \to ab$, $bB \to bb$, $bC \to bc$, $cC \to cc$: alle in der Form $\alpha A \beta \to \alpha \gamma \beta$ mit Kontext links (das Terminal) und Ersetzung der Variable durch ein Terminal. Also klassisch kontextsensitiv, längenmonoton.

Schritt 2 · Restriktivste Klasse bestimmen

Die Regel $CB \to BC$ hat zwei Variablen auf der linken Seite und schließt damit Typ 2 aus. Alle Regeln sind längenmonoton (rechte Seite mindestens so lang wie die linke). Damit ist die Grammatik Typ 1 (kontextsensitiv).

Schritt 3 · Sprache identifizieren (Zusatz)

Durch Ableitung ergibt sich $L(G) = \{\, a^n b^n c^n \mid n \ge 1 \,\}$ — die klassische kontextsensitive Beispielsprache, die nachweislich nicht kontextfrei ist. Das bestätigt die Einordnung: die Sprache ist nicht kontextfrei, also kann die Grammatik nicht Typ 2 sein.

Ableitung eines konkreten Worts $a^2 b^2 c^2$

S ⇒ aSBC        (P1)
  ⇒ a·aBC·BC    (P2, in S eingesetzt) = aaBCBC
  ⇒ aaBBCC      (P3, CB → BC)
  ⇒ aabBCC      (P4, aB → ab)
  ⇒ aabbCC      (P5, bB → bb)
  ⇒ aabbcC      (P6, bC → bc)
  ⇒ aabbcc      (P7, cC → cc)

4 · Hierarchie im Überblick

Typ	Produktionsform	Automat	Beispielsprache
0	$\alpha \to \beta$, $\alpha$ enthält Variable	Turingmaschine	rekursiv aufzählbar
1	$\alpha A \beta \to \alpha \gamma \beta$, $\|\gamma\| \ge 1$	linear beschränkter Automat	$a^n b^n c^n$
2	$A \to \beta$, $\beta$ beliebig	Kellerautomat	$a^n b^n$
3	$A \to aB \mid a \mid \varepsilon$	endlicher Automat	$a^* b^*$

   ┌───────────────────────────────────────────────────────┐
   │  Typ 0 · rekursiv aufzählbar · Turingmaschine         │
   │  ┌─────────────────────────────────────────────────┐  │
   │  │  Typ 1 · kontextsensitiv · LBA                  │  │
   │  │  ┌───────────────────────────────────────────┐  │  │
   │  │  │  Typ 2 · kontextfrei · Kellerautomat      │  │  │
   │  │  │  ┌─────────────────────────────────────┐  │  │  │
   │  │  │  │  Typ 3 · regulär · endl. Automat    │  │  │  │
   │  │  │  └─────────────────────────────────────┘  │  │  │
   │  │  └───────────────────────────────────────────┘  │  │
   │  └─────────────────────────────────────────────────┘  │
   └───────────────────────────────────────────────────────┘

5 · Rechenaufgaben mit Lösung

Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen. Alle Formeln sind mit KaTeX gesetzt.

Aufgabe 1 leicht

Klassifiziere die folgende Grammatik $G_1 = (V, \Sigma, P, S)$ mit $V = \{S, A\}$, $\Sigma = \{a, b\}$ und Produktionen:

$$P = \{\, S \to aA,\ A \to bA,\ A \to b,\ A \to \varepsilon \,\}$$

Gib den höchstmöglichen Typ der Chomsky-Hierarchie an und begründe anhand jeder einzelnen Produktion.

Lösung anzeigen

Schritt 1: Regel $S \to aA$. Linke Seite: eine Variable. Rechte Seite: ein Terminal $a$ gefolgt von einer Variablen $A$. Form $A \to aB$ ist Typ-3-konform.

Schritt 2: Regel $A \to bA$. Analog rechtslinear, Form $A \to aB$ mit Terminal $b$ und Variable $A$. Typ-3-konform.

Schritt 3: Regel $A \to b$. Form $A \to a$ mit nur einem Terminal auf der rechten Seite. Typ-3-konform.

Schritt 4: Regel $A \to \varepsilon$. Ist als Typ-3-Regel zulässig (leere rechte Seite), da $A$ eine Variable ist.

Schritt 5: Alle Regeln sind rechtslinear, keine Regel ist linkslinear. Es gibt keinen Mischformkonflikt.

Ergebnis: $G_1$ ist Typ 3 (regulär). Die erzeugte Sprache ist $L(G_1) = a \cdot b^*$.

Aufgabe 2 mittel

Klassifiziere die folgende Grammatik $G_2$ mit den Produktionen:

$$S \to aSb \mid ab \mid \varepsilon$$

Gib den höchstmöglichen Typ an und begründe, warum die Grammatik nicht Typ 3 sein kann. Bestimme zusätzlich die erzeugte Sprache.

Lösung anzeigen

Schritt 1: Regel $S \to aSb$. Linke Seite: eine Variable. Rechte Seite: Terminal $a$, Variable $S$, Terminal $b$. Nach der Variable steht noch ein Terminal — das verletzt die rechtslineare Form $A \to aB$ (dort darf nach der Variable nichts mehr folgen).

Schritt 2: Die verletzende Regel disqualifiziert Typ 3. Regel $S \to ab$ hat zwei Terminale hintereinander — auch nicht rechtslinear (Typ 3 erlaubt nur $A \to a$ mit genau einem Terminal).

Schritt 3: Alle Regeln haben genau eine Variable auf der linken Seite und keinen Kontext. Damit erfüllen sie die kontextfreie Form $A \to \beta$.

Schritt 4: Sprache bestimmen: Aus $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \dots \Rightarrow a^n S b^n$ terminiert mit $S \to ab$ zu $a^{n+1} b^{n+1}$ oder mit $S \to \varepsilon$ zu $a^n b^n$. Insgesamt:

$$L(G_2) = \{\, a^n b^n \mid n \ge 0 \,\}$$

Schritt 5: Diese Sprache ist nachweislich nicht regulär (Pumping-Lemma), was zusätzlich bestätigt, dass keine Typ-3-Grammatik existieren kann, die $L(G_2)$ erzeugt.

Ergebnis: $G_2$ ist Typ 2 (kontextfrei), nicht Typ 3.

Aufgabe 3 mittel

Gib eine Grammatik möglichst hohen Typs an, die die folgende Sprache erzeugt:

$$L = \{\, w \in \{a, b\}^* \mid w \text{ enthält eine gerade Anzahl von } a \,\}$$

Zeige die Ableitung des Wortes $baab$ und begründe den Typ.

Lösung anzeigen

Schritt 1: Die Anzahl $a$ modulo 2 lässt sich mit zwei Zuständen zählen — daher ist die Sprache regulär und eine Typ-3-Grammatik möglich.

Schritt 2: Setze $V = \{S, U\}$, wobei $S$ = gerade Anzahl $a$ bisher, $U$ = ungerade Anzahl $a$ bisher. Startsymbol $S$.

Schritt 3: Produktionen konstruieren (jeder Buchstabe wechselt oder erhält die Parität):

$$\begin{aligned} S &\to bS \mid aU \mid \varepsilon \\ U &\to bU \mid aS \end{aligned}$$

Schritt 4: Prüfe die Form: alle Regeln sind $A \to aB$, $A \to \varepsilon$ oder Terminal-Ableitungen — rechtslinear, also Typ 3.

Schritt 5: Ableitung von $baab$:

$$S \Rightarrow bS \Rightarrow baU \Rightarrow baaS \Rightarrow baabS \Rightarrow baab\varepsilon = baab$$

Schritt 6: Endzustand: nach dem letzten $a$ ist Parität gerade $\Rightarrow$ Zustand $S$ $\Rightarrow$ $S \to \varepsilon$ akzeptiert. Zwei $a$s in $baab$, also gerade Anzahl. Korrekt.

Ergebnis: Die Grammatik ist Typ 3 (rechtslinear) und erzeugt $L$.

Aufgabe 4 mittel

Gegeben sei die rechtslineare Grammatik $G$ mit $V = \{S, A, B\}$, $\Sigma = \{0, 1\}$ und Produktionen:

$$S \to 0A \mid 1B, \quad A \to 0S \mid 1A \mid \varepsilon, \quad B \to 1S \mid 0B$$

Konstruiere einen NFA $M = (Z, \Sigma, \delta, z_0, E)$ mit $L(M) = L(G)$. Gib die Übergangstabelle an.

Lösung anzeigen

Schritt 1: Konstruktionsprinzip. Aus $A \to aB$ wird Übergang $\delta(A, a) \ni B$. Aus $A \to a$ wird Übergang $\delta(A, a) \ni q_f$ (neuer Endzustand). Aus $A \to \varepsilon$ wird $A \in E$.

Schritt 2: Zustandsmenge: $Z = \{S, A, B\}$. Da wir nur $\varepsilon$-Regeln haben (keine Regeln der Form $X \to a$ ohne Folgevariable), benötigen wir keinen zusätzlichen Endzustand $q_f$.

Schritt 3: Startzustand $z_0 = S$. Endzustandsmenge $E = \{A\}$ wegen $A \to \varepsilon$.

Schritt 4: Übergangsfunktion $\delta$:

$\delta$	$0$	$1$
$\to S$	$\{A\}$	$\{B\}$
$* A$	$\{S\}$	$\{A\}$
$B$	$\{B\}$	$\{S\}$

Schritt 5: Formal:

$$M = (\{S, A, B\}, \{0, 1\}, \delta, S, \{A\})$$

Schritt 6: Verifikation mit Wort $001$: $S \xrightarrow{0} A \xrightarrow{0} S \xrightarrow{1} B$. $B \notin E$, also nicht akzeptiert. Ableitung in $G$: $S \Rightarrow 0A \Rightarrow 00S \Rightarrow 001B$. Kein Terminal-Abschluss möglich (nur über $A \to \varepsilon$), also nicht in $L(G)$. Übereinstimmend.

Ergebnis: Der NFA $M$ akzeptiert exakt $L(G)$.

Aufgabe 5 mittel

Gegeben sei der NFA $M = (Z, \Sigma, \delta, z_0, E)$ mit $Z = \{q_0, q_1, q_2\}$, $\Sigma = \{a, b\}$, $z_0 = q_0$, $E = \{q_2\}$ und der Übergangstabelle:

$\delta$	$a$	$b$
$\to q_0$	$\{q_0, q_1\}$	$\{q_0\}$
$q_1$	$\emptyset$	$\{q_2\}$
$* q_2$	$\emptyset$	$\emptyset$

Konstruiere eine rechtslineare Grammatik $G$ mit $L(G) = L(M)$.

Lösung anzeigen

Schritt 1: Umkehrkonstruktion. Setze $V = Z = \{q_0, q_1, q_2\}$, Startsymbol $S = q_0$. Für jeden Übergang $\delta(q, a) \ni p$ füge Regel $q \to a p$ hinzu. Für jeden Endzustand $q \in E$ füge $q \to \varepsilon$ hinzu.

Schritt 2: Übergänge $\delta(q_0, a) = \{q_0, q_1\}$ liefern $q_0 \to a q_0$ und $q_0 \to a q_1$.

Schritt 3: Übergang $\delta(q_0, b) = \{q_0\}$ liefert $q_0 \to b q_0$.

Schritt 4: Übergang $\delta(q_1, b) = \{q_2\}$ liefert $q_1 \to b q_2$.

Schritt 5: Endzustand $q_2 \in E$ liefert $q_2 \to \varepsilon$.

Schritt 6: Zusammengefasst:

$$\begin{aligned} q_0 &\to a q_0 \mid a q_1 \mid b q_0 \\ q_1 &\to b q_2 \\ q_2 &\to \varepsilon \end{aligned}$$

Schritt 7: Prüfung mit Wort $aab$: $q_0 \Rightarrow a q_0 \Rightarrow a a q_1 \Rightarrow a a b q_2 \Rightarrow aab \varepsilon = aab$. Wort akzeptiert. Analog im NFA: $q_0 \xrightarrow{a} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \in E$.

Ergebnis: $G$ ist rechtslinear (Typ 3) und erzeugt $L(M) = \Sigma^* \cdot ab$, d.h. alle Wörter über $\{a, b\}$, die mit $ab$ enden.

Aufgabe 6 schwer

Betrachte die Grammatik $G_6$ mit den Produktionen:

$$S \to aSa \mid bSb \mid a \mid b \mid \varepsilon$$

a) Bestimme den höchstmöglichen Typ von $G_6$.
b) Beweise formal, dass $G_6$ nicht als Typ-3-Grammatik umgeschrieben werden kann. Argumentiere über die Sprache und das Pumping-Lemma für reguläre Sprachen.

Lösung anzeigen

Schritt 1: Regelform prüfen. Alle Regeln haben eine Variable links, rechte Seiten sind aber $aSa$, $bSb$ — Variable in der Mitte, Terminale auf beiden Seiten. Nicht rechtslinear (Terminal nach der Variable). Nicht linkslinear (Terminal vor und nach der Variable). Also höchstens Typ 2.

Schritt 2: Alle Regeln haben genau eine Variable links, kontextfreie Form $A \to \beta$ ist erfüllt. Also ist $G_6$ genau Typ 2.

Schritt 3: Sprache identifizieren: $L(G_6) = \{\, w \in \{a, b\}^* \mid w = w^R \,\}$, die Menge aller Palindrome über $\{a, b\}$.

Schritt 4: Widerspruchsbeweis: Angenommen, $L(G_6)$ wäre regulär. Dann existiert nach Pumping-Lemma eine Pumping-Länge $n \ge 1$, sodass jedes $w \in L$ mit $|w| \ge n$ zerlegbar ist als $w = xyz$ mit $|xy| \le n$, $|y| \ge 1$ und $xy^i z \in L$ für alle $i \ge 0$.

Schritt 5: Wähle $w = a^n b a^n \in L$ (Palindrom, Länge $2n + 1 \ge n$). Da $|xy| \le n$, liegen $x$ und $y$ vollständig im ersten $a^n$-Block, also besteht $y$ nur aus $a$s: $y = a^k$ mit $1 \le k \le n$.

Schritt 6: Pumpe: $xy^2 z = a^{n+k} b a^n$. Da $k \ge 1$, ist $n + k \ne n$, also ist $a^{n+k} b a^n$ kein Palindrom. Damit $xy^2 z \notin L$.

Schritt 7: Widerspruch zum Pumping-Lemma. Also ist $L(G_6)$ nicht regulär. Insbesondere kann $L(G_6)$ von keiner Typ-3-Grammatik erzeugt werden.

Ergebnis: $G_6$ ist genau Typ 2 und nicht als Typ-3-Grammatik umschreibbar, weil bereits die erzeugte Sprache (Palindrome) nicht regulär ist.

Aufgabe 7 schwer

Klassifiziere die folgende Grammatik $G_7$ vollständig (Typ 0, 1, 2 oder 3) und ordne ihr das passende Automatenmodell zu. $V = \{S, A, B, T\}$, $\Sigma = \{a, b\}$:

$$\begin{aligned} S &\to AB T \\ A B &\to B A \\ T &\to a T \mid b T \mid \varepsilon \\ A &\to a \\ B &\to b \end{aligned}$$

Wende die Klassifikation systematisch an (jede Regel einzeln) und benenne die restriktivste Klasse.

Lösung anzeigen

Schritt 1: Regel $S \to ABT$. Eine Variable links, drei Variablen rechts. Kontextfrei-Form $A \to \beta$ erfüllt. Kandidat für Typ 2. Nicht rechtslinear.

Schritt 2: Regel $AB \to BA$. Linke Seite hat zwei Variablen — Typ 2 ausgeschlossen. Länge links $= 2$, Länge rechts $= 2$, längenmonoton. Diese Regel lässt sich zwar nicht direkt in die Form $\alpha A \beta \to \alpha \gamma \beta$ pressen, aber die weiter gefasste Definition von Typ 1 als längenmonotone Grammatik (äquivalent via Kuroda-Normalform) erlaubt sie. Also Typ 1 zulässig.

Schritt 3: Regel $T \to aT \mid bT \mid \varepsilon$. Rechtslineare Form $A \to aB$ bzw. $A \to \varepsilon$. Für sich genommen Typ 3.

Schritt 4: Regeln $A \to a$ und $B \to b$. Form $A \to a$, Typ-3-konform. Aber Achtung: $\varepsilon$-Regel für $T$ ist nur in Typ 1 zulässig, wenn $T$ nicht auf rechter Seite steht. $T$ steht in $S \to ABT$ auf der rechten Seite. Für Typ 1 ist $T \to \varepsilon$ trotzdem via Umformung darstellbar, muss aber für die Klausur-Definition beachtet werden.

Schritt 5: Restriktivste Klasse. Wegen $AB \to BA$ scheidet Typ 2 aus. Alle Regeln sind längenmonoton (kein Regel-Kandidat verkürzt), außer $T \to \varepsilon$. Diese ist im engeren Sinn nicht längenmonoton, aber der Standardtrick ist: Behandle $\varepsilon$-Regeln durch Vorabschluss (Ersetzung aller Vorkommen von $T$ in rechten Seiten durch Duplikat mit und ohne $T$). Danach ist die Grammatik längenmonoton äquivalent.

Schritt 6: Damit ist $G_7$ höchstens Typ 1 (kontextsensitiv), und alle Regeln lassen sich in einer längenmonotonen Grammatik ausdrücken.

Schritt 7: Automatenmodell: Typ 1 $\Leftrightarrow$ linear beschränkter Automat (LBA), also eine Turingmaschine, deren Bandlänge linear in der Eingabelänge beschränkt ist.

Ergebnis: $G_7$ ist Typ 1. Passendes Automatenmodell: LBA. Die verletzende Regel gegen Typ 2 ist $AB \to BA$ (zwei Variablen links).

6 · Typische Klausurfragen · Lesen & Argumentieren

Aufgabentyp A · Grammatik einordnen

Gegeben ist eine Produktionsmenge. Gefragt: höchster Typ der Chomsky-Hierarchie. Lesen: jede Regel einzeln durchprüfen, die restriktivste Bedingung dominiert. Falle: rechtslinear und linkslinear ist erlaubt, aber Mischformen wie $A \to Ba$ und $A \to aB$ in derselben Grammatik sind nicht mehr rechtslinear und damit nicht Typ 3 im engen Sinn.

Aufgabentyp B · Sprache klassifizieren

Gegeben eine Sprache $L$. Gefragt: höchste Klasse in der Hierarchie. Lesen: hier zählt die Sprache, nicht die Grammatik. Für Nachweis der Nicht-Regularität hilft das Pumping-Lemma; für Nicht-Kontextfreiheit das Pumping-Lemma für kontextfreie Sprachen. Falle: einige nicht-kontextfreie Sprachen erscheinen einfach (z. B. $\{ a^n b^n c^n \}$).

Aufgabentyp C · Ableitung nachvollziehen

Eine Folge von Ableitungsschritten ist gegeben. Gefragt: welche Regel wurde in welchem Schritt angewendet, oder: ist die Ableitung gültig? Lesen: linke Seite jeder Regel muss irgendwo als Teilwort in der Satzform vorkommen. Falle: mehrere Regeln passen; der Prüfer erwartet die konkret angewendete.

Aufgabentyp D · Automatenmodell zuordnen

Zu einem Typ soll das minimal ausreichende Automatenmodell benannt werden — oder umgekehrt. Falle: Kellerautomaten sind nur nichtdeterministisch äquivalent zu Typ 2, deterministisch akzeptieren sie nur eine echte Teilmenge.

7 · Fragen zum Selbsttest

Was ist der Unterschied zwischen einer Typ-2- und einer Typ-3-Grammatik?

Beide erlauben auf der linken Seite genau eine Variable. Der Unterschied liegt auf der rechten Seite: Typ 3 erlaubt nur $aB$, $a$ oder $\varepsilon$ — höchstens ein Terminal, gefolgt von höchstens einer Variable, wobei die Variable immer rechts stehen muss (rechtslinear). Typ 2 erlaubt eine beliebige Folge aus Terminalen und Variablen. Regeln wie $A \to aBa$ oder $A \to BC$ sind damit Typ 2, aber nicht Typ 3.

Warum ist $\{a^n b^n \mid n \ge 0\}$ nicht regulär, aber kontextfrei?

Ein endlicher Automat hat nur endlich viele Zustände und kann daher die Anzahl der bereits gelesenen $a$s nicht für beliebig große $n$ speichern — formal beweisbar mit dem Pumping-Lemma für reguläre Sprachen. Ein Kellerautomat kann jedoch jedes gelesene $a$ auf den Keller legen und beim Lesen der $b$s wieder abbauen; die Anzahl wird also implizit über die Kellergröße repräsentiert. Die passende Grammatik $S \to aSb \mid \varepsilon$ ist Typ 2.

Welchen Typ hat die Grammatik mit den Regeln $S \to aS$, $S \to Sa$, $S \to \varepsilon$?

Beide Regeln $S \to aS$ (rechtslinear) und $S \to Sa$ (linkslinear) sind einzeln Typ 3, aber gemischt nicht mehr im engen Sinn Typ 3, weil rechts- und linkslinear nicht innerhalb derselben Grammatik zulässig sind. Die Grammatik ist daher Typ 2 (kontextfrei). Interessanterweise ist die erzeugte Sprache $L = a^*$ trotzdem regulär — die Sprache ist Typ 3, die Grammatik aber nur Typ 2. Das illustriert, dass Grammatik-Typ und Sprach-Typ nicht dasselbe sind.

Ist jede Typ-1-Grammatik auch Typ 0? Warum?

Ja. Die Klassen sind ineinander geschachtelt: jede kontextsensitive Grammatik erfüllt automatisch die Definition von Typ 0, denn die einzige Zusatzforderung bei Typ 1 (Längenmonotonie, Kontext-Erhalt) ist eine Einschränkung, keine Erweiterung. Formal gilt $\text{Typ 3} \subseteq \text{Typ 2} \subseteq \text{Typ 1} \subseteq \text{Typ 0}$ als Mengen von Grammatiken.

Welche Sprache erzeugt $S \to aSb \mid ab$? Welchen Typ hat die Grammatik?

Die Grammatik erzeugt $L = \{\, a^n b^n \mid n \ge 1 \,\}$. Ableitung z. B. $S \Rightarrow aSb \Rightarrow aabb$. Die Grammatik ist Typ 2: linke Seite je eine Variable, rechte Seite frei. Sie ist nicht Typ 3, weil in $aSb$ nach dem $S$ noch ein Terminal folgt — das verletzt die rechtslineare Form.

Ist die Regel $AB \to BA$ in einer Typ-1-Grammatik erlaubt?

Die weiter gefasste Definition von Typ 1 als längenmonotone Grammatik erlaubt sie, denn $|AB| = |BA| = 2$. In der engeren Definition $\alpha A \beta \to \alpha \gamma \beta$ lässt sie sich nicht direkt ausdrücken, ist aber durch einen Standardtrick über Hilfsvariablen (Kuroda-Normalform) simulierbar. Beide Definitionen erzeugen dieselbe Klasse, deshalb ist die Antwort für Klausurzwecke: ja, in Typ 1 zulässig, sofern man die längenmonotone Formulierung verwendet.

Wie erkennt man in der Klausur schnell, dass eine Grammatik nicht Typ 1 ist?

Man sucht nach einer Regel, deren rechte Seite kürzer ist als die linke — mit der einzigen Ausnahme $S \to \varepsilon$ für das Startsymbol, das dann nirgends auf einer rechten Seite auftauchen darf. Findet sich eine solche verkürzende Regel (z. B. $ABC \to A$), ist die Grammatik nicht mehr längenmonoton und damit nur noch Typ 0.

Welches Automatenmodell entspricht welchem Typ?

Typ 0 $\leftrightarrow$ Turingmaschine; Typ 1 $\leftrightarrow$ linear beschränkter Automat (Turingmaschine mit Band linear beschränkt in der Eingabelänge); Typ 2 $\leftrightarrow$ nichtdeterministischer Kellerautomat (PDA); Typ 3 $\leftrightarrow$ endlicher Automat (DFA oder NFA, äquivalent). Wichtig: der deterministische Kellerautomat akzeptiert nur eine echte Teilmenge der kontextfreien Sprachen (die deterministisch kontextfreien).

Zeige, dass die erzeugte Sprache einer Typ-3-Grammatik immer regulär ist.

Aus einer rechtslinearen Grammatik $G = (V, \Sigma, P, S)$ konstruiert man einen NFA $M$ mit Zustandsmenge $V \cup \{q_f\}$, Startzustand $S$, Endzustand $q_f$. Für jede Regel $A \to aB$ setzt man einen Übergang $\delta(A, a) \ni B$; für jede Regel $A \to a$ einen Übergang $\delta(A, a) \ni q_f$; für $A \to \varepsilon$ wird $A$ zum Endzustand. Man zeigt per Induktion über die Ableitungslänge, dass $S \Rightarrow^* w$ genau dann gilt, wenn $M$ das Wort $w$ akzeptiert. Damit ist $L(G) = L(M)$, und $L(M)$ ist per Definition regulär.

Warum ist die Klassifikations-Antwort immer die kleinste (restriktivste) passende Klasse?

Weil die Klassen ineinander geschachtelt sind, erfüllt eine Typ-3-Grammatik automatisch die Bedingungen aller höheren Typen. Auf die Frage nach dem Typ könnte man formal 3, 2, 1 oder 0 antworten — alle sind korrekt, aber informativ ist nur die engste. In der Klausur wird deshalb stets die höchste Typ-Zahl (= restriktivste Klasse) verlangt, für die alle Produktionen zulässig sind.

8 · Dos & Donts in der Klausur

Dos

Regeln einzeln auf die Form prüfen, nicht die Sprache raten.
Höchste passende Typ-Zahl als Antwort geben.
Bei kontextfreien Grammatiken auf gemischte rechts-/linkslinear-Fallen achten.
Automatenmodell und Beispielsprache je Typ auswendig können.
Bei Ableitungen jeden Schritt mit der angewendeten Regel-Nummer beschriften.

Donts

Nicht Sprache und Grammatik-Typ verwechseln — sie können unterschiedlich sein.
Nicht vergessen: eine einzige verletzende Regel disqualifiziert die ganze Grammatik.
Kein Typ 3 behaupten, wenn zwei Terminale hintereinander in einer Regel stehen ($A \to abB$ ist nicht rechtslinear).
Nicht annehmen, dass jede längenmonotone Regel offensichtlich kontextsensitiv ist — man muss die Form $\alpha A \beta \to \alpha \gamma \beta$ oder die Kuroda-Normalform erwähnen.
Nicht $\varepsilon$-Regeln unbedacht in Typ-1-Grammatiken verstreuen — sie sind nur für das Startsymbol unter Zusatzbedingung erlaubt.