← Dashboard

Kapitel 07 · Theoretische Informatik

Kellerautomaten (PDA)

Klausur-Relevanz: sehr hoch · Lesen UND Rechnen

Nichtdeterministische Automaten mit Stack — das Akzeptor-Modell für die kontextfreien Sprachen (Typ 2).

TL;DR

1. Definitionen & Formalismen

Kellerautomat (formal)

Ein Kellerautomat ist ein 7-Tupel

$$M = (Z, \Sigma, \Gamma, \delta, z_0, \#, E)$$

Konfiguration

Eine Konfiguration beschreibt den vollständigen Momentanzustand des PDA und ist ein Tripel $(z, w, \gamma) \in Z \times \Sigma^* \times \Gamma^*$.

Die Startkonfiguration lautet $(z_0, w, \#)$. Ein Übergang wird mit $\vdash$ notiert.

Übergangsschritt

Aus $\delta(z, a, A) \ni (z', B_1 B_2 \dots B_k)$ folgt

$$(z, aw, A\gamma) \;\vdash\; (z', w, B_1 B_2 \dots B_k \, \gamma)$$

Das oberste Kellerzeichen $A$ wird durch das Wort $B_1 \dots B_k$ ersetzt. Bei $\varepsilon$-Übergängen ($a = \varepsilon$) wird kein Eingabezeichen konsumiert.

Akzeptanz durch Endzustand — $L(M)$

$$L(M) = \{\, w \in \Sigma^* \mid (z_0, w, \#) \;\vdash^*\; (z, \varepsilon, \gamma) \text{ für ein } z \in E, \gamma \in \Gamma^* \,\}$$

Das Wort $w$ wird akzeptiert, wenn nach vollständigem Lesen ein Endzustand erreichbar ist. Kellerinhalt am Ende beliebig.

Akzeptanz durch leeren Keller — $N(M)$

$$N(M) = \{\, w \in \Sigma^* \mid (z_0, w, \#) \;\vdash^*\; (z, \varepsilon, \varepsilon) \text{ für ein } z \in Z \,\}$$

Das Wort $w$ wird akzeptiert, wenn nach vollständigem Lesen der Keller leer ist. Zustand am Ende beliebig; $E$ irrelevant.

Satz. Beide Akzeptanzarten sind gleich mächtig: Zu jedem PDA mit Endzustands-Akzeptanz existiert ein PDA mit Leerkeller-Akzeptanz, der dieselbe Sprache erkennt — und umgekehrt.

PDA und Typ-2-Sprachen

Eine Sprache $L$ ist genau dann kontextfrei, wenn ein PDA $M$ existiert mit $L = L(M)$.

Die Klasse der von PDAs erkannten Sprachen fällt zusammen mit der Klasse der von kontextfreien Grammatiken erzeugten Sprachen.

Deterministischer PDA (DPDA)

Ein PDA heißt deterministisch, wenn für alle $z \in Z$, $A \in \Gamma$ gilt: entweder ist $\delta(z, \varepsilon, A) = \emptyset$ und $|\delta(z, a, A)| \leq 1$ für alle $a$, oder aber $\delta(z, a, A) = \emptyset$ für alle $a \in \Sigma$.

Kurz: keine Konflikte zwischen $\varepsilon$- und Symbol-Übergängen und höchstens ein Nachfolger pro Situation.

Wichtig. DPDAs sind echt schwächer als PDAs. Die Sprache der Palindrome $L = \{\, w w^R \mid w \in \{a,b\}^* \,\}$ ist kontextfrei, aber nicht deterministisch kontextfrei — kein DPDA erkennt sie.

2. Kernkonzepte & Vorgehen

  1. Sprache verstehen. Formuliere zuerst in Worten, welche Bedingungen ein Wort in $L$ erfüllen muss. Zählen ($a^n b^n$), Spiegeln ($w w^R$), Verhältnisse ($2 \cdot |a| = |b|$)? Das bestimmt, was der Stack merken soll.
  2. Stack-Strategie festlegen. Der Keller ist ein LIFO-Gedächtnis. Typische Muster: pushe Marker pro gelesenem Zeichen, poppe später im Verhältnis. Der Keller ist die einzige unbegrenzte Ressource.
  3. Zustände als Phasen. Zustände unterscheiden Phasen (z. B. ich lese noch $a$, ich lese jetzt $b$). Kombiniere Zustandsinformation mit Stack-Information — beides zusammen kodiert den vollständigen Kontext.
  4. Nichtdeterminismus nutzen. Für Palindrome oder Sprachen mit Mittelpunkt: rate den Umschaltpunkt per $\varepsilon$-Übergang. Das ist erlaubt und für viele CFL nötig.
  5. Akzeptanzart wählen. Für Klausurpapier ist Leerkeller-Akzeptanz oft eleganter (kein $E$ nötig), Endzustands-Akzeptanz ist deskriptiver, wenn Zustandsstruktur wichtig ist.
  6. Konfigurationsfolge ausschreiben. Bei Aufgaben verfolge das Wort $w$ jede Konfiguration einzeln notieren als $(z, \text{Resteingabe}, \text{Kellerinhalt}) \vdash \dots$ — die Nachvollziehbarkeit ist der bewertete Teil.

3. Beispiel durchgerechnet

PDA für $L = \{\, a^n b^n \mid n \geq 1 \,\}$

Wir konstruieren einen PDA mit Endzustands-Akzeptanz. Idee: pushe für jedes gelesene $a$ ein Zeichen $A$ auf den Stack, poppe für jedes $b$ ein $A$ wieder herunter. Am Ende muss nur noch das Bodensymbol $\#$ da liegen.

$M = (Z, \Sigma, \Gamma, \delta, z_0, \#, E)$ mit

Übergangsfunktion $\delta$:

δ(z₀, a, #) = { (z₀, A#) }        // erstes a: pushe A auf Boden
δ(z₀, a, A) = { (z₀, AA)  }        // weitere a: pushe A
δ(z₀, b, A) = { (z₁, ε)   }        // erstes b: Phase wechseln, poppe A
δ(z₁, b, A) = { (z₁, ε)   }        // weitere b: poppe A
δ(z₁, ε, #) = { (z_f, #)  }        // Boden erreicht: akzeptiere

Zustandsdiagramm

              a, # / A#           b, A / ε
              a, A / AA
        ┌──────┐             ┌──────┐             ┌──────┐
   →──▶ │  z₀  │ ─────────▶  │  z₁  │ ─────────▶  │ z_f  │  ((Endzustand))
        └──────┘             └──────┘   ε, #/#    └──────┘
                             b, A / ε
                             (Selbstschleife)

Konfigurationsfolge für $w = aaabbb$

0. (z₀, aaabbb, #) # Start
1. ⊢ (z₀, aabbb, A#) # δ(z₀,a,#) push A
2. ⊢ (z₀, abbb, AA#) # δ(z₀,a,A) push A
3. ⊢ (z₀, bbb, AAA#) # drittes a: push A
4. ⊢ (z₁, bb, AA#) # δ(z₀,b,A) Phasenwechsel, pop
5. ⊢ (z₁, b, A#) # δ(z₁,b,A) pop
6. ⊢ (z₁, ε, #) # letztes b: pop, Boden sichtbar
7. ⊢ (z_f, ε, #) # ε-Übergang in Endzustand

Da $z_f \in E$ und die Eingabe vollständig gelesen ist, gilt $aaabbb \in L(M)$. ✓

Gegenprobe: $w = aab$

0. (z₀, aab, #)
1. ⊢ (z₀, ab, A#)
2. ⊢ (z₀, b, AA#)
3. ⊢ (z₁, ε, A#) # Eingabe leer, aber A noch auf Stack

$\delta(z_1, \varepsilon, A)$ ist nicht definiert und $z_1 \notin E$. Es gibt keinen Übergang zu einem Endzustand mit leerer Resteingabe. Also $aab \notin L(M)$. ✓

4. Rechenaufgaben mit Lösung

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

Aufgabe 1 · PDA konstruieren (Leerkeller) leicht

Konstruiere einen Kellerautomaten $M = (Z, \Sigma, \Gamma, \delta, z_0, \#)$, der die Sprache $L = \{\, a^n b^n \mid n \geq 0 \,\}$ durch leeren Keller akzeptiert. Gib das 6-Tupel und alle Übergänge $\delta$ vollständig an. Achte insbesondere auf den Randfall $n = 0$ (leeres Wort $\varepsilon$).

Lösung anzeigen
Schritt 1: Strategie festlegen. Wir pushen für jedes gelesene $a$ ein Marker-Symbol $A$ auf den Stack. Sobald das erste $b$ kommt, wechseln wir die Phase und poppen für jedes $b$ ein $A$. Am Ende muss auch das Bodensymbol $\#$ entfernt werden, da wir Leerkeller-Akzeptanz nutzen. Der Randfall $n = 0$ verlangt einen $\varepsilon$-Übergang, der den Keller sofort leert.
Schritt 2: Komponenten festlegen. $Z = \{z_0, z_1\}$, $\Sigma = \{a, b\}$, $\Gamma = \{A, \#\}$, Startzustand $z_0$, Bodensymbol $\#$. Bei Leerkeller-Akzeptanz ist $E$ nicht Teil des Tupels.
Schritt 3: $\delta$ als Tabelle formulieren.
#$\delta(z, a, X)$Wirkung
1$\delta(z_0, a, \#) = \{(z_0, A\#)\}$erstes $a$: push $A$
2$\delta(z_0, a, A) = \{(z_0, AA)\}$weiteres $a$: push $A$
3$\delta(z_0, b, A) = \{(z_1, \varepsilon)\}$erstes $b$: Phasenwechsel, pop
4$\delta(z_1, b, A) = \{(z_1, \varepsilon)\}$weiteres $b$: pop
5$\delta(z_1, \varepsilon, \#) = \{(z_1, \varepsilon)\}$Boden entfernen, Keller leer
6$\delta(z_0, \varepsilon, \#) = \{(z_1, \varepsilon)\}$Randfall $n = 0$: sofort leeren
Schritt 4: Probe mit $w = aabb$. Konfigurationsfolge: $(z_0, aabb, \#) \vdash (z_0, abb, A\#) \vdash (z_0, bb, AA\#) \vdash (z_1, b, A\#) \vdash (z_1, \varepsilon, \#) \vdash (z_1, \varepsilon, \varepsilon)$. Keller leer, Eingabe leer, also $aabb \in N(M)$.
Schritt 5: Probe mit $w = \varepsilon$. $(z_0, \varepsilon, \#) \vdash (z_1, \varepsilon, \varepsilon)$ per Regel 6. Also $\varepsilon \in N(M)$, wie gefordert.
Ergebnis: Das 6-Tupel $M = (\{z_0, z_1\}, \{a,b\}, \{A, \#\}, \delta, z_0, \#)$ mit obiger $\delta$-Tabelle erkennt $L = \{a^n b^n \mid n \geq 0\}$ durch leeren Keller.
Aufgabe 2 · PDA für Palindrome mittel

Konstruiere einen PDA für die Sprache $L = \{\, w w^R \mid w \in \{a, b\}^* \,\}$ (Palindrome gerader Länge). Nutze Endzustands-Akzeptanz und begründe kurz, warum du Nichtdeterminismus benötigst.

Lösung anzeigen
Schritt 1: Idee. In der ersten Phase pushen wir das gelesene Zeichen 1:1 auf den Stack (also $a \to A$, $b \to B$). Irgendwann raten wir per $\varepsilon$-Übergang die Wortmitte und wechseln in eine Vergleichsphase, in der jedes gelesene Zeichen mit dem obersten Kellerzeichen matchen muss. Ohne Nichtdeterminismus: die Mitte $|w|$ ist ohne Lookahead nicht erkennbar, deshalb ist ein DPDA hier unmöglich.
Schritt 2: 7-Tupel. $M = (Z, \Sigma, \Gamma, \delta, z_0, \#, E)$ mit $Z = \{z_0, z_1, z_f\}$, $\Sigma = \{a, b\}$, $\Gamma = \{A, B, \#\}$, $E = \{z_f\}$.
Schritt 3: Übergänge (Push-Phase in $z_0$).
#ÜbergangBedeutung
1$\delta(z_0, a, \#) = \{(z_0, A\#)\}$push $A$ auf Boden
2$\delta(z_0, b, \#) = \{(z_0, B\#)\}$push $B$ auf Boden
3$\delta(z_0, a, A) = \{(z_0, AA)\}$push $A$
4$\delta(z_0, a, B) = \{(z_0, AB)\}$push $A$
5$\delta(z_0, b, A) = \{(z_0, BA)\}$push $B$
6$\delta(z_0, b, B) = \{(z_0, BB)\}$push $B$
Schritt 4: Umschalten per $\varepsilon$ (die Wortmitte raten).
#ÜbergangBedeutung
7$\delta(z_0, \varepsilon, A) = \{(z_1, A)\}$Mitte raten, Phase wechseln
8$\delta(z_0, \varepsilon, B) = \{(z_1, B)\}$Mitte raten, Phase wechseln
9$\delta(z_0, \varepsilon, \#) = \{(z_1, \#)\}$Fall $w = \varepsilon$: leeres Palindrom
Schritt 5: Vergleichs-Phase in $z_1$ und Akzeptanz.
#ÜbergangBedeutung
10$\delta(z_1, a, A) = \{(z_1, \varepsilon)\}$$a$ matcht $A$: pop
11$\delta(z_1, b, B) = \{(z_1, \varepsilon)\}$$b$ matcht $B$: pop
12$\delta(z_1, \varepsilon, \#) = \{(z_f, \#)\}$Boden sichtbar: akzeptiere
Schritt 6: Probe mit $w = abba$. $(z_0, abba, \#) \vdash (z_0, bba, A\#) \vdash (z_0, ba, BA\#) \vdash_{\varepsilon} (z_1, ba, BA\#) \vdash (z_1, a, A\#) \vdash (z_1, \varepsilon, \#) \vdash (z_f, \varepsilon, \#)$. Da $z_f \in E$, akzeptiert.
Ergebnis: $M$ akzeptiert genau $\{w w^R \mid w \in \{a,b\}^*\}$. Ein DPDA für diese Sprache existiert nicht (klassisches Ergebnis, DCFL $\subsetneq$ CFL).
Aufgabe 3 · Konfigurationsfolge nachvollziehen leicht

Gegeben sei der PDA aus dem Beispiel oben mit $\delta(z_0, a, \#) = \{(z_0, A\#)\}$, $\delta(z_0, a, A) = \{(z_0, AA)\}$, $\delta(z_0, b, A) = \{(z_1, \varepsilon)\}$, $\delta(z_1, b, A) = \{(z_1, \varepsilon)\}$, $\delta(z_1, \varepsilon, \#) = \{(z_f, \#)\}$ und $E = \{z_f\}$. Führe die vollständige Konfigurationsfolge für das Eingabewort $w = aabb$ aus und entscheide, ob $w \in L(M)$.

Lösung anzeigen
Schritt 1: Startkonfiguration festlegen: $(z_0, aabb, \#)$. Eingabe hat Länge 4, Keller enthält nur das Bodensymbol.
Schritt 2: Erstes Zeichen $a$, Top $\#$. Regel: $\delta(z_0, a, \#) = \{(z_0, A\#)\}$. Neue Konfiguration: $(z_0, abb, A\#)$.
Schritt 3: Zweites Zeichen $a$, Top $A$. Regel: $\delta(z_0, a, A) = \{(z_0, AA)\}$. Neue Konfiguration: $(z_0, bb, AA\#)$.
Schritt 4: Drittes Zeichen $b$, Top $A$. Regel: $\delta(z_0, b, A) = \{(z_1, \varepsilon)\}$. Wir wechseln in Phase 2 und poppen. Neue Konfiguration: $(z_1, b, A\#)$.
Schritt 5: Viertes Zeichen $b$, Top $A$. Regel: $\delta(z_1, b, A) = \{(z_1, \varepsilon)\}$. Pop. Neue Konfiguration: $(z_1, \varepsilon, \#)$.
Schritt 6: Eingabe ist leer, Top ist $\#$. $\varepsilon$-Regel: $\delta(z_1, \varepsilon, \#) = \{(z_f, \#)\}$. Neue Konfiguration: $(z_f, \varepsilon, \#)$.
Schritt 7: Kompakte Notation der Kette: $$(z_0, aabb, \#) \vdash (z_0, abb, A\#) \vdash (z_0, bb, AA\#) \vdash (z_1, b, A\#) \vdash (z_1, \varepsilon, \#) \vdash (z_f, \varepsilon, \#)$$
Ergebnis: Da $z_f \in E$ und die Resteingabe leer ist, gilt $aabb \in L(M)$. Der Automat akzeptiert das Wort.
Aufgabe 4 · CFG in CNF $\to$ PDA (Leerkeller) mittel

Gegeben die kontextfreie Grammatik $G = (V, \Sigma, P, S)$ in Chomsky-Normalform mit $V = \{S, A, B\}$, $\Sigma = \{a, b\}$ und den Produktionen

$$S \to AB, \quad S \to AC, \quad C \to SB, \quad A \to a, \quad B \to b$$

Konstruiere einen PDA $M$, der $L(G)$ durch leeren Keller akzeptiert. Nutze die Standard-Konstruktion mit einem einzigen Zustand.

Lösung anzeigen
Schritt 1: Standard-Konstruktion aus der Vorlesung. Der PDA hat nur einen Zustand $z$, das Kelleralphabet ist $\Gamma = V \cup \Sigma$, und der Startkeller enthält das Startsymbol $S$. Für jede Produktion $X \to \alpha$ gibt es einen $\varepsilon$-Übergang, der $X$ auf dem Stack durch $\alpha$ ersetzt. Für jedes Terminal $a$ gibt es einen Übergang, der ein gelesenes $a$ mit dem obersten Kellerzeichen matcht und dieses poppt.
Schritt 2: Komponenten festlegen. $Z = \{z\}$, $\Sigma = \{a, b\}$, $\Gamma = \{S, A, B, C, a, b\}$, Startzustand $z$, Bodensymbol $S$ (das Startsymbol dient hier direkt als Startkeller).
Schritt 3: Übergänge aus den Produktionen (Expandieren per $\varepsilon$).
ProduktionPDA-Übergang
$S \to AB$$\delta(z, \varepsilon, S) \ni (z, AB)$
$S \to AC$$\delta(z, \varepsilon, S) \ni (z, AC)$
$C \to SB$$\delta(z, \varepsilon, C) \ni (z, SB)$
$A \to a$$\delta(z, \varepsilon, A) \ni (z, a)$
$B \to b$$\delta(z, \varepsilon, B) \ni (z, b)$
Schritt 4: Match-Übergänge für Terminale.
TerminalPDA-Übergang
$a$$\delta(z, a, a) = \{(z, \varepsilon)\}$
$b$$\delta(z, b, b) = \{(z, \varepsilon)\}$
Schritt 5: Probe mit $w = aabb$ (Ableitung $S \Rightarrow AC \Rightarrow aC \Rightarrow aSB \Rightarrow aABB \Rightarrow aaBB \Rightarrow aabB \Rightarrow aabb$). Wichtige Konfigurationen: $(z, aabb, S) \vdash_\varepsilon (z, aabb, AC) \vdash_\varepsilon (z, aabb, aC) \vdash_a (z, abb, C) \vdash_\varepsilon (z, abb, SB) \vdash_\varepsilon (z, abb, ABB) \vdash_\varepsilon (z, abb, aBB) \vdash_a (z, bb, BB) \vdash_\varepsilon (z, bb, bB) \vdash_b (z, b, B) \vdash_\varepsilon (z, b, b) \vdash_b (z, \varepsilon, \varepsilon)$. Keller leer, Eingabe leer, akzeptiert.
Ergebnis: Der einzustandige PDA $M = (\{z\}, \{a,b\}, \{S, A, B, C, a, b\}, \delta, z, S)$ akzeptiert $L(G)$ durch leeren Keller. Die Konstruktion ist unabhängig davon, ob $G$ in CNF vorliegt — CNF erleichtert nur das nachträgliche Argumentieren über Ableitungslängen.
Aufgabe 5 · CYK-Algorithmus vollständig ausgefüllt schwer

Gegeben die kontextfreie Grammatik $G$ in Chomsky-Normalform mit Startsymbol $S$ und Produktionen

$$S \to AB \mid BC, \quad A \to BA \mid a, \quad B \to CC \mid b, \quad C \to AB \mid a$$

Prüfe mit dem CYK-Algorithmus, ob das Wort $w = baaba$ (Länge $n = 5$) in $L(G)$ liegt. Fülle die vollständige CYK-Tabelle $V_{i,j}$ mit $1 \leq i \leq j \leq 5$ aus und begründe die Antwort.

Lösung anzeigen
Schritt 1: Wort indexieren. $w_1 = b$, $w_2 = a$, $w_3 = a$, $w_4 = b$, $w_5 = a$. Die CYK-Tabelle enthält Mengen $V_{i,j}$ von Nichtterminalen, die den Teilstring $w_i \dots w_j$ ableiten können.
Schritt 2: Diagonale (Länge 1) mit den unären Regeln $A \to a$, $C \to a$ und $B \to b$ füllen.
PositionZeichen$V_{i,i}$
$V_{1,1}$$b$$\{B\}$
$V_{2,2}$$a$$\{A, C\}$
$V_{3,3}$$a$$\{A, C\}$
$V_{4,4}$$b$$\{B\}$
$V_{5,5}$$a$$\{A, C\}$
Schritt 3: Länge 2. Für $V_{i,i+1}$ prüfe $V_{i,i} \cdot V_{i+1,i+1}$ gegen alle Produktionen $X \to YZ$.
  • $V_{1,2}$: $\{B\} \cdot \{A,C\} = \{BA, BC\}$. Regeln matchen: $A \to BA$ liefert $A$; $S \to BC$ liefert $S$. Also $V_{1,2} = \{A, S\}$.
  • $V_{2,3}$: $\{A,C\} \cdot \{A,C\} = \{AA, AC, CA, CC\}$. Regeln matchen: $B \to CC$ liefert $B$. Also $V_{2,3} = \{B\}$.
  • $V_{3,4}$: $\{A,C\} \cdot \{B\} = \{AB, CB\}$. Regeln matchen: $S \to AB$ liefert $S$; $C \to AB$ liefert $C$. Also $V_{3,4} = \{S, C\}$.
  • $V_{4,5}$: $\{B\} \cdot \{A,C\} = \{BA, BC\}$. Wie $V_{1,2}$: $V_{4,5} = \{A, S\}$.
Schritt 4: Länge 3. Für $V_{i,i+2}$ betrachte alle Splits $k \in \{i, i+1\}$: $V_{i,k} \cdot V_{k+1, i+2}$.
  • $V_{1,3}$: Splits $V_{1,1} V_{2,3} = \{B\}\{B\} = \{BB\}$ (keine Regel); $V_{1,2} V_{3,3} = \{A,S\}\{A,C\} = \{AA, AC, SA, SC\}$ (keine Regel). $V_{1,3} = \emptyset$.
  • $V_{2,4}$: $V_{2,2} V_{3,4} = \{A,C\}\{S,C\} = \{AS, AC, CS, CC\}$. Regel $B \to CC$ matcht: $B$. Split $V_{2,3} V_{4,4} = \{B\}\{B\} = \{BB\}$ nichts. Also $V_{2,4} = \{B\}$.
  • $V_{3,5}$: $V_{3,3} V_{4,5} = \{A,C\}\{A,S\} = \{AA, AS, CA, CS\}$ nichts. $V_{3,4} V_{5,5} = \{S,C\}\{A,C\} = \{SA, SC, CA, CC\}$. Regel $B \to CC$ matcht: $B$. Also $V_{3,5} = \{B\}$.
Schritt 5: Länge 4. Splits $k \in \{i, i+1, i+2\}$.
  • $V_{1,4}$: $V_{1,1} V_{2,4} = \{B\}\{B\}$ nichts; $V_{1,2} V_{3,4} = \{A,S\}\{S,C\} = \{AS, AC, SS, SC\}$ nichts; $V_{1,3} V_{4,4} = \emptyset$. Also $V_{1,4} = \emptyset$.
  • $V_{2,5}$: $V_{2,2} V_{3,5} = \{A,C\}\{B\} = \{AB, CB\}$. Regeln $S \to AB$ und $C \to AB$ matchen: $\{S, C\}$. $V_{2,3} V_{4,5} = \{B\}\{A,S\} = \{BA, BS\}$. Regel $A \to BA$ matcht: $A$. $V_{2,4} V_{5,5} = \{B\}\{A,C\} = \{BA, BC\}$. Regeln $A \to BA$ und $S \to BC$ matchen: $\{A, S\}$. Vereinigung: $V_{2,5} = \{S, C, A\}$.
Schritt 6: Länge 5 — die Spitze der Tabelle. $V_{1,5}$ mit Splits $k \in \{1,2,3,4\}$.
  • $k=1$: $V_{1,1} V_{2,5} = \{B\}\{S,C,A\} = \{BS, BC, BA\}$. Regel $A \to BA$ matcht: $A$. Regel $S \to BC$ matcht: $S$.
  • $k=2$: $V_{1,2} V_{3,5} = \{A,S\}\{B\} = \{AB, SB\}$. Regeln $S \to AB$ und $C \to AB$ matchen: $\{S, C\}$.
  • $k=3$: $V_{1,3} V_{4,5} = \emptyset$.
  • $k=4$: $V_{1,4} V_{5,5} = \emptyset$.
Vereinigung: $V_{1,5} = \{A, S, C\}$.
Schritt 7: Vollständige CYK-Tabelle. Zeile = Länge $\ell = j - i + 1$, Spalte = $i$.
$\ell$$i=1$$i=2$$i=3$$i=4$$i=5$
1$\{B\}$$\{A,C\}$$\{A,C\}$$\{B\}$$\{A,C\}$
2$\{A,S\}$$\{B\}$$\{S,C\}$$\{A,S\}$—
3$\emptyset$$\{B\}$$\{B\}$——
4$\emptyset$$\{S,C,A\}$———
5$\{A,S,C\}$————
Ergebnis: Das Startsymbol $S$ liegt in $V_{1,5}$, also gilt $w = baaba \in L(G)$. Der CYK-Algorithmus bestätigt Zugehörigkeit in Zeit $\mathcal{O}(n^3 \cdot |P|)$.

5. Typische Klausurfragen (Lesen!)

Typ A — Konfigurationsfolge nachvollziehen

Gegeben ein PDA $M$ und ein Wort $w$. Aufgabe: Gib die Konfigurationsfolge $(z_0, w, \#) \vdash^* \dots$ an und entscheide, ob $w$ akzeptiert wird. Falle: bei Nichtdeterminismus musst du eine akzeptierende Berechnung finden — es genügt, dass eine existiert.

Typ B — Sprache eines PDA bestimmen

Gegeben eine $\delta$-Tabelle. Aufgabe: Beschreibe $L(M)$ in Mengennotation. Vorgehen: Muster erkennen (was wird gepusht, wann gepoppt, welche Phasen). Falle: Bodensymbol $\#$ als Bedingung für Akzeptanz übersehen.

Typ C — PDA zu einer Sprache konstruieren

Gegeben eine Sprache wie $L = \{\, a^n b^{2n} \mid n \geq 0 \,\}$. Aufgabe: konstruiere $\delta$. Falle: $n = 0$ (leeres Wort) wird gerne vergessen — hier braucht es einen $\varepsilon$-Übergang direkt in den Endzustand.

Typ D — Akzeptanzart umwandeln

Gegeben PDA mit Endzustands-Akzeptanz, konstruiere äquivalenten PDA mit Leerkeller-Akzeptanz (oder umgekehrt). Standard-Konstruktion: neues Bodensymbol $\$$ einfügen, spezieller Räum-Zustand, der bei Endzustand den Keller leert.

Typ E — DPDA vs PDA argumentieren

Aufgabe: Zeige, dass eine Sprache kontextfrei, aber nicht deterministisch kontextfrei ist, oder umgekehrt. Falle: nichtdeterministisch nötig muss argumentiert werden — ein einzelner DPDA-Versuch reicht als Nichtexistenzbeweis nicht.

6. Fragen zum Selbsttest

1. Wie unterscheidet sich ein PDA formal von einem endlichen Automaten?
Der PDA erweitert das 5-Tupel des DEA um ein Kelleralphabet $\Gamma$ und ein Bodensymbol $\#$ zu einem 7-Tupel. Der wesentliche Zuwachs liegt in $\delta$: Die Übergangsfunktion liest zusätzlich das oberste Kellerzeichen und liefert ein Wort aus $\Gamma^*$, das dieses Zeichen ersetzt. Der Stack ist unbegrenzt und ermöglicht das Erkennen nicht regulärer, aber kontextfreier Sprachen wie $a^n b^n$.
2. Warum ist ein PDA per Definition nichtdeterministisch?
Weil $\delta$ in die Potenzmenge $\mathcal{P}(Z \times \Gamma^*)$ abbildet, kann eine Situation mehrere gültige Nachfolgekonfigurationen haben. Das ist keine Schwäche, sondern notwendig: Zentrale kontextfreie Sprachen wie Palindrome erfordern das Raten des Umschaltpunkts, und ohne Nichtdeterminismus (also im DPDA-Modell) sind sie nicht erkennbar. Ein Wort gilt als akzeptiert, sobald mindestens eine Berechnung akzeptierend ist.
3. Was ist eine Konfiguration und wie liest man den Übergangspfeil $\vdash$?
Eine Konfiguration ist das Tripel $(z, w, \gamma)$ aus aktuellem Zustand, noch zu lesender Resteingabe und aktuellem Kellerinhalt (linkes Zeichen ist Top). Der Pfeil $\vdash$ bezeichnet einen einzelnen Übergangsschritt gemäß $\delta$. $\vdash^*$ ist die reflexiv-transitive Hülle, also beliebig viele (auch null) Schritte. Ein akzeptierender Lauf ist eine $\vdash^*$-Kette von der Startkonfiguration in eine akzeptierende Endkonfiguration.
4. Welche zwei Akzeptanzarten kennt der PDA und wie hängen sie zusammen?
Akzeptanz durch Endzustand: nach Lesen der gesamten Eingabe befindet sich der PDA in einem Zustand aus $E$, Kellerinhalt beliebig. Akzeptanz durch leeren Keller: nach Lesen der gesamten Eingabe ist der Keller leer, Zustand beliebig. Beide Modelle sind gleich mächtig — zu jedem PDA einer Art gibt es einen PDA der anderen Art, der dieselbe Sprache erkennt. Die Umwandlung nutzt einen Räum-Zustand bzw. ein zusätzliches Bodensymbol.
5. Welche Sprachklasse erkennen PDAs genau?
Die kontextfreien Sprachen, also Typ 2 der Chomsky-Hierarchie. Formal: $L$ ist kontextfrei genau dann, wenn ein PDA $M$ mit $L = L(M)$ existiert. Damit sind PDA und kontextfreie Grammatik zwei äquivalente Charakterisierungen derselben Sprachklasse. Die Umwandlung Grammatik $\to$ PDA (und zurück) ist konstruktiv und in der Vorlesung meist Bestandteil des Beweises.
6. Warum sind DPDAs echt schwächer als PDAs?
Ein DPDA darf pro Konfiguration höchstens einen Nachfolger haben und keine Konflikte zwischen $\varepsilon$- und Symbolübergängen zulassen. Damit kann er nicht mehr raten. Sprachen wie $L = \{\, w w^R \mid w \in \{a,b\}^* \,\}$ (Palindrome gerader Länge) sind kontextfrei, aber jeder deterministische Automat müsste den Umschaltpunkt kennen, ohne ihn im Wort sehen zu können — unmöglich. Also gilt $\text{DCFL} \subsetneq \text{CFL}$.
7. Wie liest man eine $\delta$-Regel wie $\delta(z, a, A) = \{(z', BC)\}$?
Interpretation: Wenn der PDA im Zustand $z$ ist, das nächste Eingabezeichen $a$ liest und $A$ das oberste Kellerzeichen ist, dann kann er in den Zustand $z'$ wechseln und ersetzt $A$ auf dem Stack durch das Wort $BC$. Nach der Ausführung ist $B$ das neue Top-Symbol (weil links = oben), gefolgt von $C$, gefolgt vom Reststack. Ist die rechte Seite $\varepsilon$, wird $A$ gepoppt und nichts gepusht.
8. Wozu dient das Bodensymbol $\#$ und darf es gepusht werden?
Das Bodensymbol $\#$ markiert das untere Ende des Stacks und ermöglicht das Erkennen von Keller leer bis auf Boden. In vielen Konstruktionen wird $\#$ nie gepoppt und dient nur als Signal; andere Konstruktionen erlauben Pop von $\#$. Für die Akzeptanz durch Endzustand ist der Rest-Kellerinhalt egal, für Akzeptanz durch leeren Keller muss auch $\#$ entfernt werden. In Klausurangaben immer prüfen, welche Konvention der Dozent verwendet.
9. Wie erkennt man beim Ablesen eines PDA, welche Sprache er akzeptiert?
Analyse in drei Schritten: Erstens Push-Verhalten identifizieren — was landet für welche Eingabezeichen im Keller? Zweitens Pop-Verhalten identifizieren — welche Eingabezeichen entfernen was? Drittens Zustandsstruktur lesen — welche Phasen unterscheidet der Automat? Aus dem Verhältnis von Push zu Pop (1:1, 1:2, gespiegelt) ergibt sich das Sprachmuster. Randfälle (leeres Wort, $\varepsilon$-Übergänge) explizit prüfen.
10. Warum genügt es bei einem PDA, eine einzige akzeptierende Berechnung zu finden?
Wegen des Nichtdeterminismus definiert man $L(M)$ als die Menge aller Wörter, für die mindestens eine Berechnung existiert, die in einer akzeptierenden Konfiguration endet. Andere Berechnungen desselben Worts dürfen scheitern oder in Sackgassen laufen. In Klausurlösungen reicht also der Nachweis eines gültigen Laufs für Zugehörigkeit. Für Nichtzugehörigkeit hingegen müsste man zeigen, dass keine Berechnung akzeptiert — das ist deutlich aufwendiger.

7. Dos & Don'ts in der Klausur

Do. Bei Konfigurationsfolgen jede Zeile mit $(z, \text{Resteingabe}, \text{Kellerinhalt})$ vollständig ausschreiben, auch wenn es viele Zeilen werden.
Don't. Nicht nur den letzten Zustand nennen — die Zwischenschritte sind der bewertete Teil.
Do. Bei Nichtdeterminismus die akzeptierende Berechnung wählen und nicht die erstbeste, die in einer Sackgasse endet.
Don't. Nicht behaupten, ein Wort sei nicht akzeptiert, nur weil ein Pfad scheitert — es müssen alle Pfade scheitern.
Do. Bei Sprachbeschreibungen die Kellerstrategie in einem Satz zusammenfassen (was wird gepusht, wann gepoppt).
Don't. Nicht DPDA und PDA gleichsetzen. Wenn die Aufgabe PDA sagt, ist Nichtdeterminismus erlaubt.
Do. Bei Konstruktionsaufgaben Randfälle ($n = 0$, leeres Wort) explizit behandeln — meist per $\varepsilon$-Übergang zu Beginn.
Don't. Nicht die Konvention linkes Zeichen = Top vergessen. Falsches Auslesen des Stack-Top ist einer der häufigsten Fehler.