Pushdown Automaton

A pushdown automaton is a finite automaton equipped with one extra piece of memory: a stack. Like a finite-state machine, it reads input one symbol at a time and moves between a finite set of states, but at each step it may also push a symbol onto the stack or pop one off. That single addition of unbounded, last-in-first-out memory is what lifts it above the finite automaton.

The stack is exactly the right amount of extra power to recognize nested structure. To check that parentheses are balanced, the machine pushes a marker for each opening bracket and pops one for each closing bracket; if the stack empties exactly when the input ends, the brackets match. This is the kind of counting that a finite automaton, with no memory beyond its current state, cannot do.

The central result is that pushdown automata recognize exactly the context-free languages. The class of languages a machine can accept is one of the standard ways to pin down where it sits in the hierarchy of computational models, alongside finite automata for regular languages and Turing machines for the computable languages. The pushdown automaton is the recognizer that corresponds to the context-free grammars.

This correspondence is the theory behind real parsers. The parsing stage of a compiler, which handles matched brackets, nested blocks, and arbitrarily deep expression grammars, is in essence a pushdown automaton driven by a context-free grammar. Adding a stack to a finite-state recognizer is the practical move that turns a tokenizer into a parser.