Pushdown Automata

Pushdown Automata (DPDA / NPDA)

A pushdown automaton is a finite automaton plus a stack. The extra memory lets PDAs recognise context‑free languages such as balanced brackets or aⁿbⁿ.

Transitions: read, pop → push

Each PDA move has three parts; any of them may be ε (empty):

Field	Meaning
read	Input symbol consumed. ε = consume nothing.
pop	Symbol that must be on top of the stack for the move to apply; it is removed. ε = no pop / no precondition.
push	String pushed onto the stack — its first character ends up on top. ε = push nothing.

A move is applicable only when its read matches the next input symbol (or is ε) and its pop matches the current stack top (or is ε).

The stack convention

• The stack is ordered bottom → top; the top is the last element.
• push: "AB" onto ["Z"] yields ["Z","B","A"] — top = A.
• The live stack panel animates pushes and pops during simulation and shows the instantaneous description.

Acceptance — by final state

AutomataLab PDAs accept by final state: the input is fully consumed and a current branch sits in an accept state. The stack need not be empty.

To model the classic empty‑stack style, push a bottom marker (e.g. Z) as the first move and add an ε‑move to an accept state once only Z remains.

DPDA vs. NPDA

• DPDA — at most one applicable move per configuration. The validator enforces this determinism. DPDAs recognise a strict subset of CFLs (e.g. deterministic CFLs).
• NPDA — explores all applicable moves breadth‑first as a true branching computation tree, accepting if any branch accepts. NPDAs recognise all context‑free languages, including ones no DPDA can (e.g. even‑length palindromes, which require guessing the midpoint).

NPDA runs are guarded against infinite ε‑loops with a step/branch limit; very wide or deep runs cap the visualised tree while the underlying run continues. See Simulation.

Declared stack alphabet (Γ)

Optionally declare the stack alphabet Γ in the toolbar (STACK (Γ)). It is declarative — it drives non‑blocking validation warnings (e.g. a pop/push symbol not in Γ) but the engine never enforces it. See Validation & Alphabets.

For the JSON schema and worked DPDA (aⁿbⁿ) and NPDA (palindrome) examples, see File Format.