A DFA has no memory beyond "which state am I in" — that's why no finite automaton can recognize {0ⁿ1ⁿ : n ≥ 0}, a language that needs to count arbitrarily high. A pushdown automaton (PDA) adds exactly one thing: a stack. It's still read-once, left-to-right over the input, but on every move it can also push or pop a symbol, and — critically — its next move can depend on what's on top of the stack.

The formal definition

A PDA is a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F), adding a stack alphabet Γ and initial stack symbol Z₀ to the DFA's pieces. Each transition is labeled input, pop/push: which input symbol to read (or ε to not read one), what has to be on top of the stack to pop (or ε to require nothing), and what to push in its place (or ε to push nothing). Nondeterminism is standard for PDAs — several transitions can match the same input/stack-top pair, and the machine accepts if any sequence of choices ends the input in an accept state.

Worked example: aⁿbⁿ

The classic PDA pushes a stack symbol A for every a it reads, then pops one A for every b. The initial stack symbol (here $) sits underneath everything as a marker for "nothing left to pop" — the machine only accepts after popping it too, which can only happen once every pushed A has already been popped one-for-one.

PDA: aⁿbⁿ (equal a's then b's)

Open in full simulator ↗

Trace aabb: push A, push A (stack: A A $), pop A on the first b, pop A on the second b (stack: $), then the final ε-move pops $ and lands in the accept state. Try aab or abb — the counts don't match, and there's no sequence of moves that empties the stack down to just $ at the same instant the input runs out.

Nondeterministic PDAs (NDPA)

The simulator also supports NDPA, a PDA where nondeterminism is used deliberately rather than just tolerated — useful for languages like palindromes, where the machine has to guess where the middle of the string is before it can start popping instead of pushing. Deterministic PDAs (where every state's moves are unambiguous, DPDA) recognize a strictly smaller class of languages than general PDAs do — unlike the DFA/NFA case, determinism actually costs expressive power here.