Beyond Finite Memory
A pushdown automaton extends a finite automaton with a single, unbounded stack — a last-in-first-out memory structure. This modest addition dramatically increases computational power: PDAs can recognize nested, recursive structures that no finite automaton can handle. The classic example is balanced parentheses: push on '(' and pop on ')', accepting only if the stack is empty at the end.
The Stack in Action
As the PDA reads each input symbol, it consults a transition function that depends on the current state, the input symbol (or epsilon for spontaneous moves), and the top stack symbol. The transition specifies the next state and a string to push onto the stack (possibly popping the current top first). This three-way decision — state, input, stack top — gives PDAs enough power to parse programming languages, XML documents, and mathematical expressions.
Context-Free Languages
The languages PDAs recognize are exactly the context-free languages, generated by context-free grammars. These grammars use recursive production rules like S → aSb | ε to describe nested structures. The Chomsky Normal Form ensures any CFG can be parsed in O(n³) time by the CYK algorithm, while practical LL and LR parsers achieve linear time on deterministic subsets used in real programming languages.
Parsing in Practice
Every compiler contains a pushdown automaton. When GCC parses your C code, an LR(1) parser — a deterministic PDA — verifies syntactic correctness in a single left-to-right pass. The parser's stack mirrors the nesting of your code: function definitions, if-else blocks, loop bodies, and expression groupings. Understanding PDAs is understanding how machines read structured text.