Pushdown Automata

A finite control plus a stack: the machines for context-free languages.

The idea

A pushdown automaton (PDA) is a finite automaton equipped with one additional piece of memory, a stack: an unbounded store on which the machine may push a symbol or pop the top symbol, with only the top ever visible.

The stack supplies exactly what finite memory lacks. No finite automaton can check that a block of $0$s is followed by equally many $1$s, because once the input is long enough the count outruns the states available to hold it. A stack counts without bound: push a marker for each $0$, pop one for each $1$, and the string matches when the markers run out exactly as the input ends.

Each transition of a PDA reads one input symbol or none (written $\varepsilon$), pops the symbol on top of the stack, and pushes a string of stack symbols in its place; which transitions apply may depend on the state, the input symbol, and the popped symbol. The machine accepts a string when some run ends in an accept state, or, under the other common convention, ends with the stack empty.

The class this machine captures is the reason for defining it: a language is context-free if and only if some pushdown automaton recognizes it. Grammars generate the strings and stack machines test them, and the two reach the same class. Nondeterminism is essential to the equivalence: a PDA that must commit to one transition at every point recognizes strictly fewer languages.

Ways to work on it

• Walkthrough. How a stack lets an automaton count, and why pushdown automata match context-free grammars.
• Practice. Trace a pushdown automaton's stack through an input string.
• Hardest. Design a pushdown automaton for a language built from two counting conditions.

Not sure where to start? Take the ten-question placement test.