Pushdown Automata

A finite-state machine has a fatal limitation: it cannot count. With only a fixed number of states, it can't remember "how many opening brackets have I seen?" when that number can grow without limit. So no FSM can recognise balanced brackets like ((())), or the language a^{n}b^{n}.

Give the machine a stack — a memory that can grow as tall as it likes, but which you can only push to and pop from the top — and suddenly it can. A finite-state machine plus a stack is a pushdown automaton (PDA). The stack is exactly the unlimited, last-in-first-out memory an FSM was missing.

A stack turns "count" into "push and pop"

The trick is to record counting on the stack instead of in states. To check balanced brackets: push a marker every time you see (, and pop one every time you see ). If you ever try to pop an empty stack, there was an unmatched ); if the stack is empty at the very end, every bracket matched. The stack has done the counting the states never could.

// A pushdown automaton in miniature: the array `stack` is its unbounded memory. function balanced(input: string): boolean { const stack: string[] = []; for (const ch of input) { if (ch === "(") { stack.push("("); // push on an opening bracket } else if (ch === ")") { if (stack.length === 0) return false; // nothing to match this ")" stack.pop(); // pop on a closing bracket } } return stack.length === 0; // accept only if the stack ends empty } console.log("((())) ->", balanced("((()))")); // true console.log("(() ->", balanced("(()")); // false: one left over console.log(")( ->", balanced(")(")); // false: pop on empty console.log("(a(b)c) ->", balanced("(a(b)c)")); // true: other chars ignored

This is the whole idea behind a PDA: transitions may read the input and push or pop the stack. The finite states still track "where am I in the pattern", but the stack supplies the unbounded memory.

Where PDAs sit in the hierarchy

The languages a PDA can recognise are exactly the context-free languages — the ones described by a context-free grammar, and a strict superset of the regular languages an FSM handles. That makes the PDA the middle rung of a ladder of ever-more-powerful machines:

A Turing machine replaces the one-ended stack with a tape it can move over and rewrite freely — more memory freedom again, and the top of the ladder.

Programming languages are full of nested structure: brackets inside brackets, blocks inside blocks, expressions inside expressions. Checking that they nest correctly is exactly the balanced-bracket problem, so the parser at the heart of every compiler uses a stack — it is a pushdown automaton. This is also why a plain regular expression famously cannot fully parse HTML: nesting needs a stack, and regexes don't have one.