A pushdown automaton (PDA) is a finite-state automaton augmented with an auxiliary stack that provides unbounded memory organized in a last-in-first-out discipline. This simple extension dramatically increases computational power: while finite-state automata can only recognize regular languages, pushdown automata can recognize the full class of context-free languages. Since context-free grammars are the primary formalism for phrase-structure syntax, pushdown automata provide the computational model underlying most parsing algorithms in natural language processing.
Formal Definition
A pushdown automaton is a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F), where Q is a finite set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the transition function mapping Q × (Σ ∪ {ε}) × Γ to finite subsets of Q × Γ*, q₀ is the start state, Z₀ is the initial stack symbol, and F is the set of accepting states. At each step, the PDA reads an input symbol (or makes an ε-transition), examines the top of the stack, and based on these and the current state, moves to a new state while replacing the top stack symbol with a string of stack symbols.
A move (q', γ) ∈ δ(q, a, Z) means: in state q, reading a, with Z on top,
go to q', pop Z, and push γ onto the stack.
Equivalence with Context-Free Grammars
The fundamental theorem connecting pushdown automata to context-free grammars states that a language is context-free if and only if it is accepted by some nondeterministic PDA. The construction from grammar to PDA simulates a leftmost derivation: the stack holds the predicted symbols yet to be matched, and each grammar rule corresponds to a stack replacement. Conversely, the construction from PDA to grammar encodes the stack behavior into non-terminal symbols that track the state transitions between push and pop operations.
Unlike finite-state automata, where deterministic and nondeterministic versions have equal power, deterministic pushdown automata (DPDAs) are strictly less powerful than nondeterministic PDAs. The deterministic CFL class — languages recognized by DPDAs — is a proper subset of the context-free languages. Notably, the language of palindromes {w w^R | w ∈ {a,b}*} is context-free but not deterministic context-free. This distinction matters for parsing: LR parsers handle deterministic CFLs efficiently, while general CFG parsing requires the nondeterminism captured by algorithms like Earley's.
Parsing as Stack Computation
Virtually all parsing algorithms for context-free grammars can be understood as controlled simulations of pushdown automata. Top-down (predictive) parsers operate the PDA in a predictive mode, expanding non-terminals on the stack. Bottom-up (shift-reduce) parsers use the stack to accumulate recognized phrases before reducing them. The CYK and Earley algorithms can be viewed as simulating a PDA while tabulating intermediate results to avoid redundant computation. Understanding parsing through the lens of pushdown automata provides a unified framework for comparing and analyzing different parsing strategies.
In modern computational linguistics, the PDA model also connects to ongoing research on the computational expressiveness of neural networks. Recurrent neural networks with external memory (such as stack-augmented RNNs) are explicitly designed to approximate pushdown computation. Understanding which architectural modifications allow neural models to handle context-free patterns — and which do not — is an active area of research at the intersection of formal language theory and deep learning.