Y2HLYes to Happy Learning

Courses / TOC / Topic 16

CO3 Topic 16 of 26

CFG–PDA equivalence

by Dr. Asesh Kumar Tripathy

Grammars and pushdown automata describe exactly the same languages. Build a PDA from any CFG, and a CFG from any PDA.

You will be able to

  • Convert a CFG into a PDA that simulates leftmost derivations on its stack
  • Trace the PDA built from a grammar on an input string
  • Describe the triple construction [pXq] that turns a PDA into a CFG
  • Explain why CFGs and PDAs are equivalent

Read

  • Textbook 1, §2.2 Equivalence with context-free grammars
  • Textbook 2, §6.3 Equivalence of PDAs and CFGs
  • Textbook 3, §7.2 Pushdown automata and context-free languages

Watch

Key ideas

Theorem. A language is context-free if and only if some PDA accepts it. Both directions are constructive.

CFG → PDA (one state, empty-stack acceptance). The stack holds the part of a leftmost derivation that has not been matched yet.

  1. Start with the start symbol S on the stack.
  2. Expand: if a variable A is on top, then for each production A → α, pop A and push α, by an ε-move. The PDA guesses which production to use.
  3. Match: if a terminal a is on top and a is the next input symbol, pop it and read a.
  4. Accept when the input is used up and the stack is empty.

Formally, with the single state q:

  • δ(q, ε, A) = { (q, α) | A → α }
  • δ(q, a, a) = { (q, ε) }

If the grammar is in GNF, the two steps merge. A → aα becomes δ(q, a, A) ∋ (q, α): read a and replace A with α. Every move then reads one input symbol.

PDA → CFG (the triple construction). Start from a PDA that accepts by empty stack. Create variables [pXq], meaning: "starting in state p with X on top, the PDA can read some string and end in state q, having popped X."

  • For each transition (r, Y₁Y₂…Yₖ) ∈ δ(p, a, X), and every choice of states r₁, …, rₖ, add the production
  • [pXrₖ] → a [rY₁r₁] [r₁Y₂r₂] … [rₖ₋₁Yₖrₖ].
  • When k = 0 (a pop), this is just [pXr] → a.
  • Add S → [q₀Z₀q] for every state q.

This gives up to |Q|²·|Γ| variables. Most of them are useless and can be removed (topic 12).

Worked example

Turn S → aSb | ε into a PDA, and accept aabb.

Transitions, all in the single state q:

Kind Transition
Expand δ(q, ε, S) =
Match a δ(q, a, a) =
Match b δ(q, b, b) =

Accepting run (the stack is written top first; it starts holding S):

Step ID Move
0 (q, aabb, S)
1 (q, aabb, aSb) expand S → aSb
2 (q, abb, Sb) match a
3 (q, abb, aSbb) expand S → aSb
4 (q, bb, Sbb) match a
5 (q, bb, bb) expand S → ε
6 (q, b, b) match b
7 (q, ε, ε) match b, accept

Each expansion step follows one step of the leftmost derivation S ⇒ aSb ⇒ aaSbb ⇒ aabb.

Common mistakes

  • Pushing α backwards. Push α so that its leftmost symbol is on top. That symbol must be expanded or matched first, as in a leftmost derivation.
  • Matching a variable against input. Only terminals are matched. Variables are always expanded by ε-moves.
  • Mixing acceptance modes. The standard construction accepts by empty stack. If you need final-state acceptance, convert it as in topic 15.

Tutorial problems

  1. Given the CFG S → aA | bB, A → aS | bAA | ε, B → bS | aBB | ε, construct the equivalent PDA. Trace it on abba.
  2. Convert E → E + T | T, T → T * F | F, F → ( E ) | id into a PDA, and show an accepting run for id + id.
  3. Convert the GNF grammar S → aSB | aB, B → b into a PDA in which every move reads one symbol.
  4. The PDA from topic 15 accepts {aⁿbⁿ | n ≥ 1} by empty stack. Apply the triple construction to it, remove the useless variables, and compare the result with S → aSb | ab.
  5. Explain why the CFG → PDA construction needs nondeterminism, even for an unambiguous grammar.

Viva questions

  1. Can a language be generated by a CFG but not recognised by any PDA? Justify your answer.
  2. What is the role of the stack in a PDA, and how does it relate to derivations in a CFG?
  3. In the PDA → CFG construction, what does the variable [pXq] stand for?

Quiz