Ein Automat, erweitert um einen Last‑In‑First‑Out‑Stack als unbeschränkten Hilfsspeicher; er erkennt genau die von kontextfreien Grammatiken erzeugten Sprachen (kontextfreie Sprachen) durch Zustandsübergänge kombiniert mit Push‑ und Pop‑Operationen auf dem Stack.

Prinzip

Die Kombination aus endlicher Steuerung und LIFO‑Stack liefert eine strukturierte, unbeschränkte Speicherform, die verschachtelte, hierarchische Abhängigkeiten abbilden kann, während die Zustandsstruktur endlich bleibt.

Demonstration

Ein nichtdeterministischer Pushdown‑Automat, der bei Eingaben a^n b^n für jedes a ein Stapelsymbol pusht und für jedes b ein Symbol poppt, akzeptiert genau die ausgeglichene Sprache {a^n b^n | n≥0} nach dem leer‑Stack‑ oder Akzeptanzzustandskriterium.

Fehlanwendung

Einen Pushdown‑Automaten zur Erkennung von Sprachen heranzuziehen, die zwei unabhängige Zähler erfordern (z. B. a^n b^n c^n), oder davon auszugehen, dass deterministische PDAs (DPDAs) jede kontextfreie Sprache entscheiden können; praktische Parser‑Features (Lookahead, semantische Aktionen) mit dem formalen PDA‑Modell zu verwechseln.

Konsequenz

Richtige Anwendung bringt formale Äquivalenzen (zu kontextfreien Grammatiken und nichtdeterministischen PDAs), bildet die Grundlage für Parsing‑Algorithmen und Entscheidsbarkeitsgrenzen (Mitgliedschaft, Leerheit in der CFL‑Klasse) und trennt klar von regulären Automaten und Turing‑mächtigen Modellen.

Umkehrung

Ein endlicher Automat hat keinen Stack und kann daher keine unbeschränkt verschachtelten Abhängigkeiten erzwingen; eine Turing‑Maschine ersetzt den Stack durch ein beidseitig unbeschränktes Band und erhöht damit die Ausdruckskraft gegenüber PDAs.

Abgrenzung

Geltungsbereich sind einzelne Stack‑Pushdown‑Automaten (Unterscheidung deterministisch vs. nichtdeterministisch ist relevant); ausgeschlossen sind Mehrfachstacks, Queues, zeitliche oder probabilistische Erweiterungen sowie Stacks mit unterscheidbaren Token, sofern nicht anders angegeben.

Semantische Spannung

Spannung besteht zwischen dem theoretischen PDA (einfacher Ein‑Stack‑Ansatz) und praktischen Parserimplementierungen, die Lookahead, semantische Aktionen oder mehrere Stacks hinzufügen; ebenso zwischen deterministischen PDAs (engerer Klasse) und nichtdeterministischen PDAs (vollständige CFL‑Klasse).

Synthese

Ein Pushdown‑Automat ist eine endliche Steuerung mit einem LIFO‑Stack; die Push/Pop‑Operationen erlauben das Erkennen verschachtelter, kontextfreier Strukturen, die endlichen Automaten verschlossen bleiben.