Automata and Compilers 04 - Pushdown Automata

What Finite Automata Were Missing

Finite automata can only remember their current state, with no way to track the history of previously processed input. This limitation is why they cannot recognize languages like parenthesis matching or {aⁿbⁿ}. The previous post showed that context-free grammars can describe such languages, so what computational model corresponds to context-free grammars? It is the finite automaton augmented with an auxiliary storage device called a stack — the pushdown automaton (PDA).

The Power That a Stack Provides

A stack is a data structure that operates in last-in, first-out (LIFO) order. A pushdown automaton has all the components of a finite automaton plus a stack, and at each transition it can read the top of the stack, remove it, and push new symbols. Since the stack has no size limit, it can theoretically store an unbounded amount of information.

Does a single stack really make that much of a difference? It does. Consider how to recognize the language {aⁿbⁿ}: push a symbol onto the stack for each a read, and pop one for each b. If the stack is empty after the entire input has been consumed, the counts of a's and b's are guaranteed to be equal. Counting that was fundamentally impossible with finite automata becomes natural with the addition of a single stack.

Formal Definition of Pushdown Automata

A pushdown automaton is defined by six components.

The differences from finite automata are the addition of the stack alphabet Γ and the modified transition function. The transition function δ takes the current state, an input symbol (or ε), and the top stack symbol as input, and determines the next state and the symbol to push onto the stack. That is, δ(q, a, X) = (q', Y) means "in state q, reading input a with X on top of the stack, transition to state q' and replace X with Y."

There are two acceptance modes: acceptance by reaching a final state, and acceptance by empty stack. These two modes recognize exactly the same class of languages, and each can be converted to the other.

PDA Operation Example

Let us examine a concrete PDA that recognizes the language {aⁿbⁿ | n ≥ 1}.

States: {q₀, q₁, q₂}
Input alphabet: {a, b}
Stack alphabet: {A, Z₀}
Start state: q₀
Accepting states: {q₂}
Initial stack: Z₀

Transitions:
  δ(q₀, a, Z₀) = (q₀, AZ₀)    -- first a: push A
  δ(q₀, a, A)  = (q₀, AA)      -- subsequent a's: push A
  δ(q₀, b, A)  = (q₁, ε)       -- first b: pop A
  δ(q₁, b, A)  = (q₁, ε)       -- subsequent b's: pop A
  δ(q₁, ε, Z₀) = (q₂, Z₀)     -- input consumed, stack bottom reached: accept

Tracing the input aaabbb, each a read pushes an A onto the stack (AAA), and each b read removes one A. After the third b, only the initial symbol Z₀ remains on the stack, so the PDA transitions to the accepting state and accepts the input. If the counts of a's and b's differ, either A's remain on the stack or the stack is depleted while b's remain to be read, and acceptance fails.

Equivalence of PDAs and CFGs

Just as regular expressions and finite automata are equivalent, context-free grammars and pushdown automata are equivalent. A language being generable by a context-free grammar and being recognizable by a pushdown automaton are the same condition.

This equivalence is proved by constructing conversions in both directions. The conversion from CFG to PDA is relatively intuitive: place the start symbol on the stack, and if the top of the stack is a non-terminal, push the right-hand side of a production rule; if it is a terminal, match it against the input and pop. This is essentially a simulation of a leftmost derivation. The reverse direction, from PDA to CFG, is more complex but equally possible.

This equivalence is not merely a theoretical result. Understanding that a compiler's parser is fundamentally a pushdown automaton provides deeper insight into parser design and behavior. The parser's use of a stack to track nested structures is the operation of a PDA in its essence.

Deterministic vs. Nondeterministic PDAs

Unlike finite automata, where DFAs and NFAs recognize the same class of languages, deterministic PDAs (DPDAs) and nondeterministic PDAs (NPDAs) differ in their capabilities. This is a significant distinction.

Nondeterministic PDAs can recognize all context-free languages, but deterministic PDAs can only recognize deterministic context-free languages (DCFLs), a proper subset. For example, {wwᴿ | w ∈ {a,b}*} (the palindrome language) is a context-free language but not a deterministic context-free language, because the midpoint of the string cannot be determined deterministically.

Is this distinction practically relevant? Very much so. Practical parsers must be deterministic. A nondeterministic parser would need to explore multiple possibilities simultaneously, making efficient implementation difficult. This is why programming language grammars are generally designed to be parsable by deterministic PDAs — that is, to fall within the categories of LL or LR grammars.

Limitations of PDAs — Context-Sensitive Languages

Despite the power of a stack, a stack alone cannot recognize all languages. A canonical example is {aⁿbⁿcⁿ | n ≥ 0}. Recognizing strings where the counts of a's, b's, and c's are all equal requires counting a's while simultaneously verifying that count against both b's and c's. A stack can track the relationship between two kinds of symbols (a's and b's), but tracking the relationship among three kinds simultaneously is not possible.

Such languages belong to the class of context-sensitive languages, and recognizing them requires a more powerful model called the linear bounded automaton. Fortunately, the syntactic structure of programming languages is largely expressible with context-free grammars, so PDA-based parsers are sufficient for the parsing phase of a compiler.

In the next post, we'll look at how the theory covered so far comes together in an actual compiler — the overall phases and architecture of a compiler.