Begriff
Pushdown Automaton (PDA)
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Ein Endlicher Automat (wie ein Drehkreuz oder Cola-Automat) hat kein Gedächtnis. Er weiß nur "Zustand: Offen". Er weiß nicht, wie oft Münzen eingeworfen wurden.
Ein Kellerautomat (Pushdown Automaton) hat einen Stack (Speicher).
Er kann Münzen auf den Stapel legen (Push) und wegnehmen (Pop).
Damit kann er zählen und Klammern prüfen.
(( )): 2x Push, 2x Pop -> Stack leer -> Korrekt.
((): 2x Push, 1x Pop -> Stack nicht leer -> Fehler.
Merksatz: Ein theoretisches Maschinenmodell, das einen endlichen Automaten um einen unendlich großen Stapelspeicher (Stack) erweitert und genau die Klasse der kontextfreien Sprachen (Typ 2) erkennen kann.
Jeder Compiler-Parser ist im Herzen ein PDA.
Wenn du Java kompilierst:
opens class { opens void main() { ... } }.
Der Parser pusht "Class Scope", pusht "Method Scope".
Am Ende der Methode popt er.
Ohne Stack könnte man keine verschachtelten Blöcke parsen.
1. Deterministisch vs. Nicht-Deterministisch (DPDA vs NPDA)
Wichtig! Bei Endlichen Automaten gilt: DFA = NFA (gleich mächtig). Bei Kellerautomaten gilt: NPDA > DPDA. Nicht-Deterministische Kellerautomaten können mehr Sprachen erkennen (z. B. Palindrome ohne Markierung der Mitte "abba") als deterministische. Programmiersprachen werden meist so designed, dass sie von deterministischen PDAs (LR-Parser) geparst werden können (Effizienz).
2. Zwei Stacks?
Was passiert, wenn man einem PDA zwei Stacks gibt? Er wird zur Turing-Maschine. Er kann den zweiten Stack als "rechtes Band" und den ersten als "linkes Band" nutzen. Er wird Typ 0 (unendlich mächtig).
1. Visibly Pushdown Automata (VPA)
In der Forschung (Verifikation) nutzt man eine spezielle Klasse: VPAs.
Hier entscheidet allein das Eingabesymbol, ob gepusht oder gepopt wird (z.B. < pusht immer, > popt immer).
Der Riesenvorteil: VPAs sind unter Schnittmenge und Komplement abgeschlossen (wie endliche Automaten). Normale PDAs sind das nicht! Das erlaubt es, VPAs für das Model Checking von rekursiven Programmen (Funktionsaufrufen) zu nutzen, was mit normalen PDAs mathematisch unmöglich wäre.
2. Closure Properties und Grenzen
Was kann ein PDA nicht?
- Schnittmenge: Zwei kontextfreie Sprachen ergeben nicht zwingend eine kontextfreie Sprache (man bräuchte zwei Stacks für den Vergleich).
- Komplement: Das Gegenteil einer kontextfreien Sprache ist nicht zwingend kontextfrei. Dies ist der Grund, warum man für Sprachen wie $L = {a^n b^n c^n}$ (gleiche Anzahl a, b und c) eine Turing-Maschine braucht. Ein PDA könnte zwar prüfen, ob $n(a) = n(b)$, aber er müsste dafür seinen Stack leeren. Er hätte dann "vergessen", wie groß $n$ war, um es mit $c$ zu vergleichen.
3. Emptiness & Finiteness Problem
Kann man automatisch prüfen, ob ein PDA jemals anhält oder ob er überhaupt ein Wort akzeptiert? Ja! Für PDAs ist das Emptiness-Problem entscheidbar (im Gegensatz zur Turing-Maschine). Das wird in der statischen Code-Analyse genutzt: Man abstrahiert ein Programm als PDA (die Zustände sind die Programmzeilen, der Stack sind die Funktionsaufrufe). Dann kann man mathematisch beweisen: "Diesen Fehler-Zustand (Nullpointer) kann der Automat niemals erreichen (Emptiness Check)."
Quick-Check
Warum "Keller"?
Deutsches Wort für Stack ("Kellerspeicher"). Man wirft Kohlen in den Keller und holt die letzten zuerst wieder raus (LIFO).HTML?
HTML ist nicht ganz kontextfrei (wegenopen tag must match close tag string). Ein reiner PDA kann nicht prüfen, ob<a>...</b>falsch ist (er speichert nur "Da war ein Tag", nicht den String "a"). Echte Parser speichern Symbol-Tabellen.Unendlicher Stack?
Theoretisch ja. Praktisch hast du 8MB Stack Size. Wenn der PDA zu tief geht -> StackOverflowError.