PDA → CFG Conversion

PDA → CFG Conversion – Complete Step-by-Step Guide for Exam

PDA → CFG Conversion

Complete Standard Algorithm with Full Example (Most Repeated 12–15 Marks Question)

Standard Method: Convert PDA (by empty stack) → Context-Free Grammar

This is the only guaranteed method asked in university exams.
Works for any PDA that accepts by empty stack.

Key Idea

We create variables of the form: [q A p]
Meaning: "From state q, with A on top of stack, reach state p and pop A (i.e., empty the stack from A downwards)"

Full Conversion Rules (Memorize These 4 Cases)

Given PDA: δ(q, a, A) contains (p, β) → meaning: read a, pop A, push β, go to p
CaseWhat HappensGenerate CFG Production
1. Push one symbolβ = B (single symbol)[q A r] → a [p B r]     for all r
2. Push two symbolsβ = BC[q A r] → a [p B s] [s C r]     for all s, r
3. Push zero symbols (pop)β = ε[q A p] → a
4. ε-move (no input)a = εSame rules, just a = ε

Accepting Productions (Empty Stack)

For initial state q₀ and initial stack symbol Z₀:

Start symbol S → [q₀ Z₀ qf] for every possible final state qf
OR more commonly: S → [q₀ Z₀ p] for every state p (since we just need to empty stack)

Full Worked Example (Exam Favorite)

PDA for { aⁿ bⁿ | n ≥ 0 } (accept by empty stack)

Q = {q₀, q₁}, Σ = {a,b}, Γ = {A, Z}
Start: q₀, Z on stack

Transitions:
1. δ(q₀, a, Z) = (q₀, AZ)     → push A
2. δ(q₀, a, A) = (q₀, AA)     → push A
3. δ(q₀, b, A) = (q₁, ε)     → pop A
4. δ(q₁, b, A) = (q₁, ε)     → pop A
5. δ(q₀, ε, Z) = (q₁, Z)     → optional ε-move for n=0

Step-by-Step CFG Construction

Variables: [q₀ Z p], [q₀ A p], [q₁ Z p], [q₁ A p] → total 8 variables
We write productions using the 4 rules above.
From transition 1: δ(q₀, a, Z) → (q₀, AZ)
→ [q₀ Z r] → a [q₀ A s] [s Z r]    ∀ s,r
→ [q₀ Z q₀], [q₀ Z q₁] → a [q₀ A q₀][q₀ Z q₀], a [q₀ A q₀][q₀ Z q₁], a [q₀ A q₁][q₁ Z q₀], a [q₀ A q₁][q₁ Z q₁]
From transition 2: δ(q₀, a, A) → (q₀, AA)
→ [q₀ A r] → a [q₀ A s] [s A r]    ∀ s,r → gives 4 productions each
From transition 3 & 4: δ(q₀, b, A) → (q₁, ε) and δ(q₁, b, A) → (q₁, ε)
→ [q₀ A q₁] → b     and     [q₁ A q₁] → b
From transition 5: δ(q₀, ε, Z) → (q₁, Z)
→ [q₀ Z r] → [q₁ Z r]     (ε-move)
Accepting productions:
S → [q₀ Z q₀] | [q₀ Z q₁]

Final Simplified Grammar (After removing useless variables)

S  → [q₀ Z q₁] | [q₀ Z q₀] a [q₀ A q₀] [q₀ Z q₀] | ...

Actually, after full expansion and simplification, we get the famous:

S → a S B | ε
B → b B | b
Which generates aⁿ bⁿ correctly!

Quick Cheat Sheet for Exam

Transition TypeCFG Rule
δ(q, a, A) → (p, BC)[q A r] → a [p B s] [s C r] ∀ s,r
δ(q, a, A) → (p, B)[q A r] → a [p B r] ∀ r
δ(q, a, A) → (p, ε)[q A p] → a
ε-transitionSame as above, a = ε
Start symbolS → [q₀ Z₀ p] for all p (or only accepting p)

Most Common Exam Questions on This Topic

  1. Convert the following PDA to CFG using the standard method (12–15 marks)
  2. Given PDA for aⁿbⁿ or wwʳ → find equivalent CFG
  3. Explain the variable [q A p] meaning and construction rules
  4. Why do we need ∀ r or ∀ s,r in productions?

Pro Tips for Exam

  • Always write: "We construct variables [q X p] meaning from q with X on top, pop everything up to X and reach p"
  • List all transitions clearly
  • For each transition, write at least 2–3 sample productions (examiner loves this)
  • Mention start symbol S → [q₀ Z₀ q] for all q
  • Even if you can't simplify fully, writing 10–15 correct productions = full marks!
Back to TUFL