CFG-PDA Equivalence

A context-free grammar $G = (V, \Sigma, R, S)$ generates strings by repeatedly rewriting a variable using a rule $A \to \alpha$, where $\alpha \in (V \cup \Sigma)^*$, starting from the start variable $S$, until no variables remain. A pushdown automaton $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$ recognizes strings by reading input left to right while maintaining a stack over alphabet $\Gamma$, where transitions may (optionally) consume an input symbol, and always specify a pop of the top stack symbol and a push of a string of stack symbols, including the empty string $\varepsilon$ for "no-op." Both models manipulate strings via a single unbounded auxiliary structure — a sentential form's unexpanded suffix for the grammar, the stack for the automaton — and the equivalence theorem says these two structures can simulate each other exactly. The precise statement: a language $L$ is context-free (i.e., $L = L(G)$ for some CFG $G$) if and only if $L = L(P)$ for some PDA $P$. Proving "only if" (CFG → PDA) shows every grammar has a recognizing machine; proving "if" (PDA → CFG) shows every stack-based recognizer has a generating grammar. Neither direction is a mere existence proof — both give explicit algorithms transforming one object into the other, which is what makes the theorem usable in practice (e.g., in the theory underlying LL/LR parsing, even though those parsers use more disciplined subclasses of PDAs). The key structural insight tying the two together is leftmost derivation order. In a leftmost derivation, at every step the leftmost variable in the sentential form is the next one expanded. This means the sentential form always looks like (matched terminal prefix)(single active variable's expansion, itself starting with more variables and terminals). A stack, which only exposes its top, can hold exactly this "remaining to be processed, in order" suffix — the terminal at the front of the stack corresponds to the next symbol that must be matched against input, and popping it and pushing a rule's right-hand side corresponds exactly to one derivation step.

Direction 1: CFG → PDA

Given CFG $G = (V, \Sigma, R, S)$, build a PDA $P$ with a single state $q$ (all "state" bookkeeping is unnecessary; the stack alone tracks progress). Initialize the stack with $S$. Then repeatedly:

• If the top of stack is a variable $A$, nondeterministically pop it and push some $\alpha$ where $A \to \alpha \in R$ (no input consumed) — this is the guess a rule move.
• If the top of stack is a terminal $a$, and the current input symbol is $a$, pop it and consume $a$ from input (this must match — no choice).

Accept if the stack empties exactly when the input is exhausted (equivalently: accept by empty stack, or add a bottom marker and a final pop-and-accept transition). ``` CFG-TO-PDA(G = (V, Σ, R, S)): // Single-state PDA; stack alphabet Γ = V ∪ Σ ∪ {⊥} states = { q } start state = q stack alphabet = V ∪ Σ ∪ {⊥} // ⊥ = bottom-of-stack marker initial stack = ⊥ S // S on top accept condition = stack contains only ⊥ (or: pop ⊥ and move to accept state) transitions δ: // 1. Expand a variable (ε-move: no input read) for each rule (A → α) in R: δ(q, ε, A) ∋ (q, α) // pop A, push α (α reversed onto stack, rightmost symbol on top... // actually push so that leftmost symbol of α ends up on top) // 2. Match a terminal against input for each terminal a in Σ: δ(q, a, a) ∋ (q, ε) // pop a, push nothing, consume input symbol a // 3. Accept: pop the bottom marker once the stack is otherwise empty δ(q, ε, ⊥) ∋ (q_accept, ε) return P = ({q, q_accept}, Σ, V ∪ Σ ∪ {⊥}, δ, q, {q_accept}) ``` A subtlety worth pinning down: pushing $\alpha = X_1 X_2 \cdots X_k$ must place $X_1$ (the leftmost symbol) on top of the stack, since leftmost derivations process left to right. Concretely the transition pushes the symbols in the order $X_k, X_{k-1}, \ldots, X_1$ so that $X_1$ ends up on top.

Direction 2: PDA → CFG

This direction is subtler. Given PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$, assume (WLOG, by standard normalization) that $P$'s transitions always push at most two symbols or pop exactly one and every accepting computation ends with an empty stack in some accepting state — these normalizations don't change $L(P)$ and simplify the construction. The grammar's variables are triples $A_{p,q}$ for $p, q \in Q$, informally meaning: > $A_{p,q}$ generates exactly the strings $w$ such that reading $w$ can drive $P$ from state $p$ (with some symbol $X$ freshly on top of the stack) to state $q$, having popped that same $X$ and left everything below it untouched. This "balanced push-then-pop" idea mirrors matched parentheses / matched grammar nonterminal expansions. ``` PDA-TO-CFG(P = (Q, Σ, Γ, δ, q0, F)): // Assumes P accepts by empty stack; every move pushes 0, 1, or 2 symbols // Variables: A[p,q] for every p, q in Q // Start variable: S = A[q0, q_f] summed (via OR-rules) over all q_f... // concretely: add rules S -> A[q0, q] for every state q (since "empty stack" already implies acceptance) V = { A[p,q] : p, q ∈ Q } ∪ { S } R = {} // Rule family 1: splitting a computation that stays at "the same stack level" for each p, q, r in Q: R += { A[p,q] -> A[p,r] A[r,q] } // Rule family 2: base case, a single stack symbol pushed and later popped for each p, q in Q, each a in Σ ∪ {ε}, each b in Σ ∪ {ε}: for each transition δ(p, a, ε) ∋ (s, X) // push X while reading a (a may be ε) for each transition δ(t, b, X) ∋ (q, ε) // pop X while reading b (b may be ε) for each intermediate state s, t with a path "doing nothing to the stack below X": R += { A[p,q] -> a A[s,t] b } // Rule family 3: empty productions (no net stack change, no symbols consumed) for each p in Q: R += { A[p,p] -> ε } // Start symbol R += { S -> A[q0, f] : f ∈ F } return G = (V, Σ, R, S) ``` The pseudocode above is the standard shape of the construction; the delicate part (elided as "for each intermediate state... doing nothing to the stack below X") is formalized cleanly in the single-pop normal form: every PDA can be converted so each transition either (a) pushes exactly one symbol and reads one input symbol, or (b) pops exactly one symbol and reads one input symbol, with no transition doing both push-and-pop simultaneously and no transitions touching two symbols at once. Under that normal form, rule family 2 becomes exact and simple:

CFG → PDA size and time. The resulting PDA has exactly one "working" state plus one accept state, and one transition per grammar rule (for variable expansions) plus one transition per terminal (for matching) plus one accept transition. So the PDA has $O(1)$ states and $O(|R| + |\Sigma|)$ transitions, where $|R|$ is the number of grammar rules — the construction is linear in the grammar's size and takes $O(|G|)$ time to build. Correctness (sketch). We show by induction on the number of derivation steps that

if and only if the PDA, after reading $w$, can have stack contents $\alpha \,\bot$ (with $\bot$ the bottom marker never otherwise touched). Base case: zero steps, $w = \varepsilon$, $\alpha = S$, stack is $S\bot$ — matches the initial configuration. Inductive step: a leftmost derivation step replaces the leftmost variable $A$ (which, by the leftmost-derivation invariant, sits at the very front of $\alpha$, i.e., on top of the stack) via a rule $A \to \beta$, and the PDA's corresponding $\varepsilon$-move pops $A$ and pushes $\beta$ — exactly reproducing the new sentential form on the stack. Symmetrically, whenever $\alpha$ begins with a terminal $a$, the leftmost derivation forces the next generated symbol to be $a$, matching precisely the PDA's terminal-consuming transition. Hence $w \in L(G)$ (i.e. $S \Rightarrow^*_{\text{lm}} w$) iff the PDA can read all of $w$ and empty the stack down to $\bot$, iff $w$ is accepted. Since every derivation has an equivalent leftmost derivation (a standard grammar fact), this argument covers all of $L(G)$, giving $L(P) = L(G)$.

PDA → CFG size and time. With $|Q|$ states and $|\delta|$ transitions (after normalizing to single-symbol push/pop form, which at most doubles/triples transition count), the grammar has $O(|Q|^2)$ variables $A_{p,q}$, and rule family 1 alone contributes $O(|Q|^3)$ rules (one for every triple $p, r, q$), while rule family 2 contributes $O(|Q|^2 \cdot |\delta|^2)$ in the naive worst case (pairing every push-transition with every matching pop-transition), though tighter bookkeeping (matching only transitions that push/pop the same stack symbol and are reachable from each other) keeps it polynomial, typically $O(|Q|^2 |\delta|)$. This is a genuine, sometimes severe, blow-up: converting a PDA to a grammar is not linear, unlike the reverse direction. Correctness (sketch). We show $A_{p,q} \Rightarrow^* w$ if and only if $P$, started in state $p$ with an arbitrary symbol $X$ on top of the stack, can consume $w$ and reach state $q$ with that same $X$ having been popped and nothing pushed below it disturbed (a "stack-neutral" computation from $p$ to $q$). This is proved by induction on the length of the PDA computation:

• If the computation from $p$ to $q$ never lets the stack drop below its starting height except at the very end (i.e., $X$ stays put until the last step), it must consist of one push (of some $X$, going to intermediate state $s$), a stack-neutral sub-computation from $s$ to some $t$ entirely above $X$, and then the matching pop of $X$ (from $t$ to $q$) — this is exactly rule family 2, $A_{p,q} \to a\,A_{s,t}\,b$.
• If instead the stack does return to its starting height partway through (at some intermediate state $r$), the computation splits into two independent stack-neutral sub-computations, $p \to r$ and $r \to q$ — this is exactly rule family 1, $A_{p,q} \to A_{p,r} A_{r,q}$.
• The base case of zero net pushes/pops is $A_{p,p} \to \varepsilon$.

Every accepting computation of $P$ (from $q_0$ to some $f \in F$ with the stack empty at both ends, given the empty-stack acceptance convention) is exactly a stack-neutral computation from $q_0$ to $f$, so $S \Rightarrow^* w$ iff $w$ drives $P$ from $q_0$ to some accepting $f$ with an empty final stack, iff $w \in L(P)$. This establishes $L(G) = L(P)$.

Honest tradeoffs. The CFG→PDA direction is cheap and is exactly what a top-down (recursive-descent / LL) parser generator effectively compiles to — but the resulting PDA is highly nondeterministic in general, which is why practical parsers restrict to deterministic subclasses (LL(1), LR(1)) rather than using this construction as-is. The PDA→CFG direction proves the theoretical ceiling but the grammar produced is usually far too large and unstructured for practical parsing; it is a proof tool, not an engineering tool.

Take the classic non-regular language $L = \{ 0^n 1^n : n \ge 0 \}$, generated by CFG $G$: $S \to 0S1 \mid \varepsilon$.

Applying CFG→PDA, we get a single-state PDA $P$ with transitions:

Trace on input $w = 0011$:

Input fully consumed, stack empty — accept, matching that $0011 \in L$.

Applying PDA→CFG on a (single-state-collapsed for illustration) PDA recognizing the same language would recover variables like $A_{q_0,q_0}$ generating exactly $\{0^n1^n\}$, with rule $A_{q_0,q_0} \to 0\, A_{q_0,q_0}\, 1$ arising from a push-of-`0`/pop-of-`0` pair, and $A_{q_0,q_0} \to \varepsilon$ from the base case — recovering, up to renaming, the very grammar $G$ we started with. This "round trip" is a good sanity check of the constructions: applying both translations in sequence does not have to reproduce the original grammar exactly (it usually produces something larger and differently structured), but it must reproduce the same language.

The theory of context-free languages and pushdown automata crystallized in the late 1950s and early 1960s, driven jointly by linguistics (Noam Chomsky's hierarchy of grammars) and early compiler theory (the need to parse ALGOL-like programming languages efficiently).

Parser generators such as Yacc, Bison, and ANTLR are direct engineering descendants of the CFG–PDA equivalence: a grammar written by a language designer is compiled into an automaton (a deterministic pushdown-like recognizer, e.g., an LALR or LL parser) that drives compilation. XML and JSON validators rely on context-free structure (matching nested tags/brackets) recognized via stack-based parsing. Network protocol parsers and configuration-file readers use recursive-descent parsers, which are hand-written instances of the CFG→PDA construction. The theorem also underlies Closure Properties of Context-Free Languages, since many closure proofs (union, concatenation, Kleene star) are most naturally phrased by combining grammars, then transported to pushdown automata via this equivalence, and vice versa for constructions that are easier to see on the machine side.

Ask the tutor: Can you walk me through converting a small ambiguous grammar into its PDA and show where the nondeterminism appears in the stack transitions?