We now have two very different descriptions of languages. A context-free grammar generates strings by rewriting variables. A pushdown automaton recognises strings by reading them with the help of a stack. It is a central result of the theory that these two describe exactly the same family of languages.
Theorem: a language L is context-free (generated by some CFG) if and only if L is accepted by some (nondeterministic) pushdown automaton, by final state or, equivalently, by empty stack.
This chapter proves both directions by construction. CFG → PDA is short and intuitive: the stack simulates a leftmost derivation. PDA → CFG is the famous "triple construction" with variables [pXq]. Both constructions are exam favourites, so we work through each one completely. The constructed machines and grammars in this chapter were checked by a simulator and a parser against the target languages for all strings up to length 8 to 12.
Throughout, we use the notation of Pushdown Automata: δ(q, a, X) ∋ (p, γ) means "in state q, reading a (or ε), with X on top: go to p, pop X, push γ with its leftmost symbol on top".
Part 1: From CFG to PDA
The idea
Think of a leftmost derivation of w. At every moment, the sentential form looks like
(terminals already matched) (the rest: starts with a variable or a terminal)
x α
The PDA keeps α on its stack, with its leftmost symbol on top, and keeps x as the part of the input already read. Then only two kinds of moves are needed:
Expand: if a variable A is on top, replace it (without reading input) by the right side of some production A → β. This is where the PDA guesses which production the derivation uses.
Match: if a terminal a is on top, it must equal the next input symbol. Read it and pop it.
When the stack is empty and the input is used up, the derivation has produced exactly w.
The construction
For a CFG G = (V, T, P, S), build a PDA with one state q that accepts by empty stack:
P = ({q}, T, V ∪ T, δ, q, S, ∅) start stack symbol = S
(1) for every variable A: δ(q, ε, A) = { (q, β) : A → β is a production } expand
(2) for every terminal a: δ(q, a, a) = { (q, ε) } match
Then N(P) = L(G). The number of transitions equals the number of productions plus the number of terminals.
Example
Grammar for { wcwR : w ∈ {a, b}* }:
S → aSa | bSb | c
PDA (one state q, stack starts with S):
δ(q, ε, S) = { (q, aSa), (q, bSb), (q, c) }
δ(q, a, a) = { (q, ε) }
δ(q, b, b) = { (q, ε) }
δ(q, c, c) = { (q, ε) }
Accepting run on abcba, shown next to the leftmost derivation it simulates:
ID (state, remaining input, stack) | Move | Sentential form = read part + stack |
|---|---|---|
(q, abcba, S) | start | S |
(q, abcba, aSa) | expand S → aSa | aSa |
(q, bcba, Sa) | match a | a · Sa |
(q, bcba, bSba) | expand S → bSb | a · bSba |
(q, cba, Sba) | match b | ab · Sba |
(q, cba, cba) | expand S → c | ab · cba |
(q, ba, ba) | match c | abc · ba |
(q, a, a) | match b | abcb · a |
(q, ε, ε) | match a | abcba (accept: empty stack, input used) |
The right column is exactly S ⇒ aSa ⇒ abSba ⇒ abcba. This invariant, "input read so far + stack contents = current left-sentential form", is the whole correctness proof in one line.
Note that this PDA is nondeterministic even though our grammar is very simple: on S it must choose among three expansions. The PDA's "guess" corresponds to a parser's decision. Predictive (LL) parsers in compilers are exactly this PDA, made deterministic by peeking at the next input symbol.
A shortcut when the grammar is in GNF
If every production is A → aα (see Greibach Normal Form), an expand move can be fused with the match of a:
for every production A → aα: δ(q, a, A) ∋ (q, α)
Now every move reads exactly one input symbol, and the PDA has no ε-moves (apart from S → ε if ε ∈ L). For the GNF grammar S → bT | b, T → aB | aBT, B → b (language b(ab)*):
δ(q, b, S) = { (q, T), (q, ε) }
δ(q, a, T) = { (q, B), (q, BT) }
δ(q, b, B) = { (q, ε) }
(q, babab, S) ⊢ (q, abab, T) ⊢ (q, bab, BT) ⊢ (q, ab, T) ⊢ (q, b, B) ⊢ (q, ε, ε)
Five input symbols, five moves.
Part 2: From PDA to CFG (the Triple Construction)
The idea
Assume the PDA P = (Q, Σ, Γ, δ, q0, Z0) accepts by empty stack (we can always convert, as shown in Pushdown Automata). The key observation is about how a PDA gets rid of one stack symbol.
Suppose X is on top. Eventually X is popped, and at that moment the stack below X is exposed for the first time. Everything in between, including pushing and popping other symbols above, is a self-contained "sub-computation". We create one grammar variable for each such possible sub-computation:
Variable [pXq] generates exactly the input strings w such that the PDA, starting in state p with X on top, can read w and end in state q having just removed X (with the stack below X never touched). In symbols: [pXq] ⇒* w iff (p, w, X) ⊢* (q, ε, ε).
The productions
Start: S → [q0 Z0 p] for every state p ∈ Q
For every transition (r, Y1 Y2 … Yk) ∈ δ(q, a, X), a ∈ Σ ∪ {ε}:
k = 0 (pop): [q X r] → a
k ≥ 1: [q X rk] → a [r Y1 r1] [r1 Y2 r2] … [r(k−1) Yk rk]
for EVERY choice of states r1, r2, …, rk ∈ Q
Read the k ≥ 1 rule as: to pop X starting in q, first read a and go to r with Y1…Yk on the stack; then pop Y1 (ending in some state r1), then pop Y2 (ending in r2), …, then pop Yk (ending in rk). Since we do not know the intermediate states in advance, we write a production for every possible guess. Wrong guesses produce variables that generate nothing, and they are removed later as useless symbols.
Counting
At most |Q|2 · |Γ| triple variables, plus S.
A transition that pushes k ≥ 1 symbols creates |Q|k productions (one for each choice of r1, …, rk). A popping transition (k = 0) creates exactly one.
The start rule creates |Q| productions.
Worked example: back to anbn
A PDA accepting { anbn : n ≥ 1 } by empty stack, with Q = {q0, q1} and Γ = {Z0, X}:
# | Transition | Meaning |
|---|---|---|
1 | δ(q0, a, Z0) = {(q0, XZ0)} | first a: push X |
2 | δ(q0, a, X) = {(q0, XX)} | more a's: push X |
3 | δ(q0, b, X) = {(q1, ε)} | first b: pop |
4 | δ(q1, b, X) = {(q1, ε)} | more b's: pop |
5 | δ(q1, ε, Z0) = {(q1, ε)} | pop Z0: accept |
Start productions (2 of them):
S → [q0 Z0 q0] | [q0 Z0 q1]
Rule 1 pushes k = 2 symbols, so 22 = 4 productions. The left side is [q0 Z0 r2]; the body is a [q0 X r1] [r1 Z0 r2]:
r1 = q0, r2 = q0: [q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0]
r1 = q1, r2 = q0: [q0 Z0 q0] → a [q0 X q1] [q1 Z0 q0]
r1 = q0, r2 = q1: [q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1]
r1 = q1, r2 = q1: [q0 Z0 q1] → a [q0 X q1] [q1 Z0 q1]
Rule 2, again 4 productions:
[q0 X q0] → a [q0 X q0] [q0 X q0]
[q0 X q0] → a [q0 X q1] [q1 X q0]
[q0 X q1] → a [q0 X q0] [q0 X q1]
[q0 X q1] → a [q0 X q1] [q1 X q1]
Rules 3, 4, 5 pop, one production each:
[q0 X q1] → b
[q1 X q1] → b
[q1 Z0 q1] → ε
That is 2 + 4 + 4 + 3 = 13 productions.
Cleaning up
Now remove useless symbols (see Simplification of CFGs).
Generating variables. Start with variables that have a terminal-only body: [q0Xq1], [q1Xq1], [q1Z0q1]. Then [q0Z0q1] → a[q0Xq1][q1Z0q1] is generating, and so is S → [q0Z0q1]. The others never generate a terminal string: [q1Xq0] and [q1Z0q0] have no productions at all (the PDA never moves from q1 back to q0), and [q0Xq0], [q0Z0q0] only have productions that use non-generating variables. Delete them and every production that mentions them.
What remains (all reachable from S):
S → [q0 Z0 q1]
[q0 Z0 q1] → a [q0 X q1] [q1 Z0 q1]
[q0 X q1] → a [q0 X q1] [q1 X q1] | b
[q1 X q1] → b
[q1 Z0 q1] → ε
Rename A = [q0Z0q1], B = [q0Xq1], C = [q1Xq1], D = [q1Z0q1] and substitute C = b, D = ε:
S → aB
B → aBb | b
which clearly generates anbn, n ≥ 1. A parser confirmed that the full 13-production grammar generates exactly { anbn : 1 ≤ n ≤ 6 } among all strings of length ≤ 12.
Derivation mirrors computation
The leftmost derivation of aabb in the triple grammar follows the PDA's run move by move:
S ⇒ [q0 Z0 q1]
⇒ a [q0 X q1] [q1 Z0 q1] rule 1: read a, push X
⇒ a a [q0 X q1] [q1 X q1] [q1 Z0 q1] rule 2: read a, push X
⇒ a a b [q1 X q1] [q1 Z0 q1] rule 3: read b, pop X
⇒ a a b b [q1 Z0 q1] rule 4: read b, pop X
⇒ a a b b rule 5: pop Z0
At each step, the variables still in the sentential form are exactly the stack contents, each annotated with the state the PDA is in when that symbol becomes the top, and the state it will be in after popping it.
Putting It Together
CFG ──(expand/match, 1 state)──► PDA by empty stack
▲ │
│ │ (equivalent)
triple construction [pXq] ▼
│ PDA by final state
└──────── PDA by empty stack ◄─────────┘
Direction | Construction | Size of result | Key idea |
|---|---|---|---|
CFG → PDA | One state; expand variables with ε-moves, match terminals | |P| + |T| transitions | Stack holds the unexpanded part of a leftmost sentential form |
GNF → PDA | One state; δ(q, a, A) ∋ (q, α) for A → aα | |P| transitions, no ε-moves | Each move reads one symbol |
PDA → CFG | Variables [pXq]; one production per transition and per guess of intermediate states | ≤ |Q|2|Γ| + 1 variables | [pXq] = "inputs that take p to q while popping X" |
Two useful consequences:
Every PDA has an equivalent PDA with a single state (accepting by empty stack). Convert PDA → CFG → PDA; the second construction uses one state. The states of a PDA add convenience, not power: the stack can carry all the information.
Closure proofs can use whichever model is easier. For example, intersection of a CFL with a regular language is shown by running a PDA and a DFA together, while union and concatenation are easiest with grammars. These are covered in Closure & Decision Properties of CFLs.
One caution: the equivalence is for nondeterministic PDAs. The CFG → PDA construction usually produces a nondeterministic machine, and some CFLs (such as wwR) have no deterministic PDA at all.
Common Mistakes
Pushing the right side in reverse. For A → aSa, push aSa with a (the leftmost symbol) on top, because the leftmost symbol must be matched first.
Forgetting the match rules δ(q, a, a) = {(q, ε)} for every terminal a.
Using the triple construction on a final-state PDA. The construction assumes acceptance by empty stack. Convert first.
Fixing the last state rk. In [q X rk] → a[r Y1 r1]…[rk−1 Yk rk], every ri ranges over all of Q, including rk, which also appears on the left side. Only the first state of the body, r, is fixed by the transition.
Forgetting the ε in ε-moves. For δ(q, ε, X) ∋ (r, ε), the production is [qXr] → ε, not [qXr] → a.
Counting productions wrongly. A move pushing k symbols gives |Q|k productions, not |Q|k+1 and not |Q|·k.
Practice and GATE-Style Questions
Q1. A PDA accepting by empty stack has 3 states and 4 stack symbols. How many variables can the triple construction produce (including S)?
3 × 4 × 3 = 36 triple variables, plus S: 37.
Q2. A PDA has 3 states. One of its transitions is δ(q, a, X) ∋ (p, YZW). How many productions does this single transition contribute?
k = 3 pushed symbols, each followed by a free state choice: 33 = 27 productions, all of the form [q X r3] → a [p Y r1][r1 Z r2][r2 W r3].
Q3. Construct a PDA for the grammar S → aSb | ab and show the run on aabb.
δ(q, ε, S) = { (q, aSb), (q, ab) }
δ(q, a, a) = { (q, ε) }, δ(q, b, b) = { (q, ε) }
(q, aabb, S) ⊢ (q, aabb, aSb) ⊢ (q, abb, Sb) ⊢ (q, abb, abb)
⊢ (q, bb, bb) ⊢ (q, b, b) ⊢ (q, ε, ε) acceptThe expand choices S → aSb, then S → ab, correspond to the leftmost derivation S ⇒ aSb ⇒ aabb.
Q4. In the triple construction, what does it mean if [pXq] has no productions at all?
Look at where productions for [pXq] come from. Every move from state p with X on top that pushes k ≥ 1 symbols gives [pXq] a production (because the last state rk ranges over all of Q, including q), and a popping move δ(p, a, X) ∋ (q, ε) gives [pXq] → a. So [pXq] has no productions exactly when the PDA has no move at all from p with X on top, except possibly popping moves that end in a state other than q. Then no input can take the PDA from p to q while removing X, the variable generates nothing, and it is deleted as useless. In the anbn example, [q1Xq0] is such a variable: the only move from q1 with X on top pops and stays in q1.
Q5. Interview: a compiler's LL parser is described as "a PDA". Which construction from this chapter is it?
The CFG → PDA construction: the parse stack holds grammar symbols, a variable on top is expanded by a production, and a terminal on top is matched with the next token. The LL(1) parsing table removes the nondeterminism by choosing the production from the top variable and one lookahead token.
Summary
CFLs = languages of nondeterministic PDAs (by final state or empty stack).
CFG → PDA: one state, empty-stack acceptance; δ(q, ε, A) for every A → β (expand), δ(q, a, a) = {(q, ε)} (match). The stack mirrors the leftmost derivation.
From a GNF grammar, δ(q, a, A) ∋ (q, α) gives a PDA with no ε-moves.
PDA → CFG: variables [pXq] meaning "go from p to q while popping X"; S → [q0Z0p]; a pop move gives [qXr] → a; a move pushing k symbols gives |Q|k productions.
Remove useless symbols at the end; most guessed triples disappear.
A grammar can be run on a stack, and a stack machine can be written as a grammar. The stack is the unfinished part of a derivation; a variable [pXq] is the story of one stack symbol from push to pop.