A finite automaton has fixed memory. Add an unbounded stack, a structure where you can only push or pop the top element, and you get the pushdown automaton (PDA). It is a small addition, but enough to recognize nested structures such as parentheses, blocks and function calls. PDAs are the operational counterpart of context-free grammars, just as DFAs are the counterpart of regular expressions.
The definition
A PDA is a 6-tuple (Q, Σ, Γ, δ, q₀, F), with two new ingredients compared with a finite automaton:
- Γ is the stack alphabet, which may contain symbols different from the input ones;
- the transition function δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × (Γ ∪ {ε})) looks at the state, the input symbol (or none) and the symbol on top of the stack (or none), and returns a set of pairs (new state, symbol to push).
A transition is often written a, X → Y: "reading a, with X on top of the stack, pop X and push Y". If X is ε nothing is popped; if Y is ε nothing is pushed.
In the standard version the PDA is nondeterministic and accepts if some computation branch consumes the whole input and ends in an accepting state.
An example: aⁿbⁿ
The PDA for {aⁿbⁿ : n ≥ 0} uses the stack as a counter:
- At the start it pushes a bottom marker, for example $.
- For every a read, it pushes an A.
- When it meets the first b, it moves to a state where, for every b, it pops an A.
- If at the end of the input $ is on top again, it pops the marker and moves to the accepting state.
If more b's than a's arrive, at some point the stack shows $ when an A is needed and the branch dies. If fewer b's arrive, the stack still holds some A's and the accepting state is not reached. If an a appears after a b, there is no transition and the branch dies.
An example that needs nondeterminism
The language of even-length palindromes, {wwᴿ : w ∈ {a, b}*}, where wᴿ is w written backwards, is recognized like this:
- Read symbols and push them onto the stack.
- At some point the PDA guesses it has reached the middle and changes state.
- From then on, each symbol read must match the one on top of the stack, which is popped.
- Accept if the stack becomes empty exactly at the end of the input.
Step 2 is essential: reading left to right there is no way to know where the middle is. Nondeterminism explores every possibility, and it is enough for one to work.
Equivalence with grammars
The central result is:
a language is context-free if and only if it is recognized by a nondeterministic pushdown automaton.
Both directions have concrete constructions.
- From grammar to PDA: the PDA pushes the start variable. If a variable is on top, it nondeterministically picks a rule and replaces the variable with the right-hand side. If a terminal is on top, it matches it against the input and pops it. It accepts when input and stack run out together. In practice it simulates a leftmost derivation.
- From PDA to grammar: build a variable Aₚq for each pair of states, generating the strings that can take the PDA from p to q while leaving the stack as it was. This is the more technical direction, but the idea is that each "push and matching pop" pair becomes a rule.
Deterministic is not enough
Unlike finite automata, for PDAs nondeterminism adds power. Deterministic PDAs (DPDAs), which have at most one possible move at each step, recognize a strictly smaller class: the deterministic context-free languages.
The language wwᴿ is an example of a context-free language that is not deterministic. If instead a separator is placed in the middle, as in {wcwᴿ}, the DPDA knows exactly when to switch behaviour and the language becomes deterministic.
This distinction has practical consequences: the parsers used in compilers, such as LR and LL parsers, are essentially DPDAs. That is why language designers write grammars that fall into the deterministic class, so that parsing runs in linear time without backtracking.
Limits of the pushdown automaton
The stack has its own limits: only the top can be read, and whatever is popped is lost. This is why a PDA cannot recognize {aⁿbⁿcⁿ}: after using the stack to compare the a's with the b's, nothing is left to check the c's. Languages of this kind need a more powerful model, such as a Turing machine or a linear bounded automaton.
In short
- A PDA is a finite automaton with an unbounded stack, accessible only from the top.
- The stack makes it possible to count and to match nested structures, as in aⁿbⁿ and palindromes.
- Nondeterministic PDAs recognize exactly the context-free languages.
- Deterministic PDAs are strictly weaker, but they underlie LL and LR parsers.
- A PDA cannot recognize aⁿbⁿcⁿ: one stack is not enough for multiple comparisons.
