Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Kellerautomaten (Pushdown-Automaten)
Ein endlicher Automat kann aⁿ bⁿ nicht erkennen, weil er nicht beliebig weit zählen kann. Gib ihm einen Stapel Papier zum Mitzählen, und plötzlich geht es. Genau das ist der Kellerautomat: ein endlicher Automat mit einem zusätzlichen, unbegrenzten Keller (Stack). Er ist das Maschinenmodell der kontextfreien Sprachen und damit die Grundlage jedes Parsers.
Was du in der Klausur können musst:
- den Kellerautomaten als 7-Tupel beschreiben
- die Keller-Operationen (push/pop, nur oben) und beide Akzeptanz-Modi
aⁿ bⁿSchritt für Schritt auf dem Keller verarbeiten- die Falle DPDA
subsetneqNPDA (anders als beim DFA/NFA)
Die Idee in einem Satz
Ein Kellerautomat (PDA, Pushdown-Automat) ist ein endlicher Automat mit einem zusätzlichen unbegrenzten Keller (Stack als Gedächtnis). Er erkennt genau die kontextfreien Sprachen (Chomsky-Typ 2).
Der Keller (Stack)
Der Keller ist ein LIFO-Speicher (last in, first out): nur das oberste Symbol ist zugänglich.
- push: ein (oder mehrere) Symbole oben drauflegen
- pop: oberstes Symbol herunternehmen
- man kann nicht in den Keller hineinschauen, nur die Spitze lesen
Der unbegrenzte Keller ist das Gedächtnis, das einem endlichen Automaten fehlt. Damit kann der PDA zählen und vergleichen, was Automaten ohne Keller nicht können.
Das formale Modell: 7-Tupel
Ein Kellerautomat ist ein M = (Q, Σ, Γ, δ, q₀, Z₀, F) mit:
| Symbol | Bedeutung |
|---|---|
Q | endliche Zustandsmenge |
Σ | Eingabealphabet |
Γ | Kelleralphabet |
δ | Überführungsfunktion Q × (Σ ∪ \ε\) × Γ → P(Q × Γ^*) |
q₀ | Startzustand |
Z₀ | Kellerbodensymbol |
F | Endzustände |
Ein Schritt liest ein Eingabesymbol oder ε, nimmt das oberste Kellersymbol herunter und legt eine (evtl. leere) Zeichenkette darauf. ε-Übergänge sind erlaubt, das unterscheidet PDAs von DFAs.
Zwei Akzeptanz-Modi (äquivalent)
Ein PDA akzeptiert ein Wort entweder
- durch Endzustand: Eingabe gelesen und in einem Zustand aus
F, oder - durch leeren Keller: Eingabe gelesen und Keller komplett abgebaut.
Beide Modi erkennen dieselbe Sprachklasse (die kontextfreien Sprachen).
Beispiel: aⁿ bⁿ auf dem Keller
Die Strategie ist Zählen per Keller: jedes a legt ein Symbol A ab, jedes b nimmt eines herunter.
q₀, liesta: legeAauf den Keller (zähle hoch)q₀, liest erstesbmitAoben: nimmAherunter, wechsle nachq₁q₁, liestbmitAoben: nimmAherunter (zähle ab)- akzeptiert, wenn Eingabe leer und Keller wieder leer ist (gleich viele
awieb)
Verfolge es Schritt für Schritt:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Determinismus: die wichtige Falle
Bei endlichen Automaten sind DFA und NFA gleich mächtig. Bei Kellerautomaten ist das anders:
DPDA
subsetneqNPDA. Deterministische Kellerautomaten erkennen nur die deterministisch kontextfreien Sprachen (DCFL), eine echte Teilmenge der kontextfreien Sprachen. Nichtdeterministische PDAs sind echt mächtiger.
Beispiel: die Palindrome \{w w^R mid w ∈ \a,b\^*\} sind kontextfrei, aber kein DPDA erkennt sie, weil er die Mitte des Wortes nicht deterministisch findet. Man braucht Nichtdeterminismus, um zu "raten", wo die Mitte ist.
Zusammenhang mit Grammatiken
Kellerautomaten und kontextfreie Grammatiken sind äquivalent: zu jeder kontextfreien Grammatik gibt es einen PDA, der dieselbe Sprache erkennt, und umgekehrt. Deshalb sind PDAs die theoretische Grundlage der Syntaxanalyse (Parser) im Compilerbau.
Klausur-Faustregeln
1. PDA = endlicher Automat + unbegrenzter Keller. Er erkennt genau die kontextfreien Sprachen (Typ 2).
2. 7-Tupel (Q, Σ, Γ, δ, q₀, Z₀, F). δ liest Eingabe oder ε, popt oben, pusht eine Zeichenkette.
3. Nur die Kellerspitze ist zugänglich (LIFO). Push und pop, kein Hineinschauen.
4. Zwei äquivalente Akzeptanz-Modi: Endzustand oder leerer Keller.
5. aⁿ bⁿ per Keller: a legt ab, b nimmt herunter. So zählt der PDA.
6. PDA ≡ kontextfreie Grammatik. Anwendung: Parser, Syntaxanalyse, BNF/EBNF.
Häufige Stolpersteine
1. DPDA und NPDA gleichsetzen. Anders als beim DFA/NFA ist der nichtdeterministische Kellerautomat echt mächtiger. DPDA subsetneq NPDA.
2. Mehrere Keller annehmen. Ein PDA hat genau einen Keller. Zwei Keller hätten bereits die Mächtigkeit einer Turing-Maschine.
3. In den Keller hineinschauen. Nur das oberste Symbol ist lesbar. Tiefer liegende Symbole erreicht man erst, wenn die oberen abgebaut sind.
4. aⁿ bⁿ cⁿ für kontextfrei halten. Diese Sprache ist nicht kontextfrei (ein Keller reicht für eine Zählung, nicht für zwei unabhängige Vergleiche). Das zeigt das Pumping-Lemma für kontextfreie Sprachen.
5. Akzeptanz-Modus vermischen. Sage klar "durch Endzustand" oder "durch leeren Keller", nicht beides gleichzeitig im selben Argument.
6. ε-Übergänge übersehen. Ein PDA darf Schritte ohne Lesen eines Eingabesymbols machen (Eingabe ε), z.B. um am Ende den Keller zu leeren.
Interaktiv verstehen
Den Keller arbeiten sehen
Wähle ein Wort und gehe Schritt für Schritt. Achte darauf, wie der Keller bei den a wächst und bei den b wieder abgebaut wird. Akzeptiert wird nur, wenn am Ende Eingabe und Keller gleichzeitig leer sind.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "aⁿ bⁿ"-artigen Sprachen ist der Keller dein Zähler. Probiere aabbb (ein b zu viel) und abab (falsche Form), um zu sehen, wie der Automat stecken bleibt oder mit nicht-leerem Keller endet.
Praxis-Übung
Klausurfragen mit Lösungen (6)
- F1.Was unterscheidet einen Kellerautomaten von einem endlichen Automaten?
Antwort: Er hat einen zusätzlichen, unbegrenzten Keller (Stack) als Gedächtnis
Erklärung: Der Kellerautomat ist ein endlicher Automat mit einem unbegrenzten Keller. Dieses Zusatzgedächtnis erlaubt das Zählen und Vergleichen, das einem endlichen Automaten fehlt.
- F2.Welche Sprachklasse erkennen Kellerautomaten?
Antwort: die kontextfreien Sprachen (Typ 2)
Erklärung: Kellerautomaten erkennen genau die kontextfreien Sprachen (Chomsky-Typ 2). Reguläre Sprachen schaffen endliche Automaten, Typ 0 die Turing-Maschine.
- F3.Ordne jeden Chomsky-Typ dem passenden Maschinenmodell zu.
Zuordnungen:
- Typ 3 (regulär) → endlicher Automat
- Typ 2 (kontextfrei) → Kellerautomat
- Typ 1 (kontextsensitiv) → linear beschränkte TM
- Typ 0 (rekursiv aufzählbar) → Turing-Maschine
Erklärung: Die Chomsky-Hierarchie: Typ 3 = endlicher Automat, Typ 2 = Kellerautomat, Typ 1 = linear beschränkte TM, Typ 0 = allgemeine Turing-Maschine. Je höher die Modellstärke, desto mehr Gedächtnis.
Typ: Zuordnung
- F4.Auf dem Kellerautomaten für aⁿ bⁿ: was passiert beim Lesen eines a im Startzustand?
Antwort: ein Symbol wird auf den Keller gelegt (push)
Erklärung: Jedes `a` legt ein Symbol auf den Keller (push), so wird die Anzahl der `a` gezählt. Beim späteren Lesen der `b` wird für jedes `b` ein Symbol heruntergenommen (pop).
- F5.Deterministische und nichtdeterministische Kellerautomaten erkennen dieselbe Sprachklasse.
Antwort: Falsch
Erklärung: Falsch. Anders als bei DFA und NFA gilt hier DPDA `subsetneq` NPDA: nichtdeterministische Kellerautomaten sind echt mächtiger. Z.B. die Palindrome `\w w^R\` erkennt kein deterministischer PDA.
Typ: Wahr/Falsch
- F6.Warum ist \aⁿ bⁿ cⁿ mid n ≥ 1\ NICHT kontextfrei?
Antwort: weil ein einzelner Keller nur eine Zählung verwalten kann, nicht zwei unabhängige Vergleiche
Erklärung: Mit einem Keller kann man `a` gegen `b` zählen, danach ist der Keller leer und die Information über `n` verloren, um auch noch die `c` zu prüfen. Zwei unabhängige Zählungen schafft ein PDA nicht. Das beweist das Pumping-Lemma für kontextfreie Sprachen.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Aus welchen Bestandteilen besteht das 7-Tupel eines PDA?
Antwort: `(Q, Σ, Γ, δ, q₀, Z₀, F)`
Erklärung: Der PDA ist ein 7-Tupel `(Q, Σ, Γ, δ, q₀, Z₀, F)` mit Zuständen, Eingabe- und Kelleralphabet, Überführungsfunktion, Start, Kellerboden und Endzuständen. Das 5-Tupel ist ein DFA, das 4-Tupel eine Grammatik.
- F2.Welche Kelleroperationen sind möglich?
Antwort: nur am obersten Element: lesen, herunternehmen (pop) und drauflegen (push)
Erklärung: Der Keller ist ein LIFO-Speicher: nur die Spitze ist zugänglich. Man liest das oberste Symbol, nimmt es herunter (pop) und legt eine Zeichenkette darauf (push). Tiefere Symbole sind nicht direkt erreichbar.
- F3.Welche beiden Akzeptanz-Modi hat ein Kellerautomat?
Antwort: durch Endzustand oder durch leeren Keller (beide äquivalent)
Erklärung: Ein PDA akzeptiert durch Erreichen eines Endzustands ODER durch vollständiges Leeren des Kellers. Beide Modi erkennen exakt dieselbe Sprachklasse (die kontextfreien Sprachen).
- F4.Ein PDA erkennt genau die {{1}} Sprachen. Nichtdeterministische PDAs sind {{2}} als deterministische. Mit zwei Kellern hätte das Modell die Mächtigkeit einer {{3}}.
Lösungen pro Lücke:
- {{1}}: kontextfreien / kontextfreie / kontextfrei
- {{2}}: mächtiger / mächtiger / stärker / stärker
- {{3}}: Turing-Maschine / Turingmaschine / TM
Erklärung: PDA = kontextfreie Sprachen. NPDA ist echt mächtiger als DPDA. Zwei Keller ergeben bereits ein turingmächtiges Modell (zwei Stacks simulieren ein Band).
Typ: Lückentext
- F5.Beim PDA für aⁿ bⁿ liest du das Wort aabb. Wie sieht der Keller nach dem Lesen von aa aus (Boden Z unten)?
Antwort: `Z A A` (zwei `A` über dem Boden)
Erklärung: Jedes `a` legt ein `A` auf den Keller. Nach `aa` liegen zwei `A` über dem Bodensymbol `Z`: also `Z A A`. Die beiden folgenden `b` nehmen die `A` wieder herunter.
- F6.Welche Sprache erfordert einen NICHTdeterministischen Kellerautomaten (kein DPDA reicht)?
Antwort: `\{w w^R mid w ∈ \a,b\^*\}` (Palindrome gerader Länge)
Erklärung: Palindrome `w w^R` sind kontextfrei, aber kein DPDA erkennt sie, weil er die Mitte des Wortes nicht deterministisch bestimmen kann. Er muss nichtdeterministisch 'raten', wo die zweite Hälfte beginnt. `aⁿ bⁿ` dagegen ist sogar deterministisch kontextfrei.
