Converting CFGs to PDAs
What you'll learn: You'll master the algorithm that transforms any context-free grammar into an equivalent pushdown automaton that recognizes the same language.
The Core Idea
Remember that PDAs and CFGs are equivalent in power—they both define exactly the context-free languages. Converting a CFG to a PDA makes this connection concrete: the PDA essentially simulates leftmost derivations of the grammar using its stack.
The algorithm creates a PDA that:
- Pushes the start symbol onto the stack
- Repeatedly expands nonterminals using production rules
- Matches terminals with input symbols
- Accepts when both input and stack are empty
The Construction Algorithm
Given a CFG G = (V, Σ, R, S), construct PDA P:
States: Three states: q_start, q_loop, q_accept
Stack alphabet: All grammar symbols (terminals and nonterminals)
Transitions:
- Initialize: From
q_starttoq_loop, push start symbolS(ε-transition) - Expand nonterminals: In
q_loop, for each productionA → w, popAand pushwin reverse order (ε-transition, no input consumed) - Match terminals: In
q_loop, for each terminala, popawhen readingafrom input - Accept: From
q_looptoq_acceptwhen stack is empty (ε-transition)
Why It Works
Think of the stack as a to-do list for the derivation. When you pop a nonterminal, you're deciding "which production rule applies here?" and pushing the right-hand side tells the PDA what to derive next. When you pop a terminal, you verify it matches the input—like checking your work against the string being parsed.
Key Takeaway: Any CFG can be mechanically converted to a PDA that uses its stack to maintain the current sentential form during a leftmost derivation, popping nonterminals to expand them and matching terminals against the input.