Finite automata are powerful, but they have a hard ceiling: they can't count. No DFA or NFA can recognize aⁿbⁿ (equal numbers of as followed by bs), because doing so requires remembering how many as you've seen, an amount of information that grows without bound, and a finite automaton only has finitely many states to hold it in.

Adding a Stack

A pushdown automaton (PDA) fixes this by bolting a stack onto a finite automaton. Formally it has seven components, (Q, Σ, Γ, δ, q0, Z0, F), where Γ is the stack alphabet and Z0 the initial stack symbol. Each transition can read an input symbol (or ε), pop the top of the stack, and push a new string of symbols in its place. That single piece of unbounded, last in, first out memory is enough to recognize any context free language.

Worked Example: aⁿbⁿ

Push a marker for every a, then pop one for every b:

On each a: push A, stay in the same state.
On the first b: pop an A, move to a second state.
On each subsequent b: pop an A, stay in the second state.
Accept if the stack holds only Z0 when input ends.

If there are more bs than as, the stack empties early and there's nothing left to pop, so the machine rejects. If there are fewer, an A is still sitting on the stack at the end, so it rejects again. Only an exact match empties the stack at exactly the right moment.

Deterministic vs Nondeterministic PDAs

Unlike finite automata, deterministic and nondeterministic PDAs are not equally powerful: DPDA languages are a strict subset of context free languages. Recognizing palindromes (w = wʳ) is the classic example that needs nondeterminism: the machine has to guess where the middle of the string is before it can start popping the stack to compare the second half against the first.

PDAs and Context Free Grammars

This isn't a coincidence: PDAs and context free grammars (CFGs) are equivalent models. Every CFG can be mechanically converted into a PDA that accepts the same language, and vice versa, which is why parser generators for programming languages are, under the hood, built around the same structure as a PDA.

Try It Yourself

Build the aⁿbⁿ machine above (or the nondeterministic palindrome checker) on the canvas and step through it symbol by symbol. The stack panel shows exactly what gets pushed and popped at each move.