CFG to PDA Conversion and PDA to CFG

🎯 Learning Objectives

• Convert any CFG to an equivalent PDA
• Convert any PDA to an equivalent CFG
• Trace the conversion step by step
• Understand the equivalence proof

1. CFG → PDA Conversion

1.1 Construction

1. Push $ (bottom) then push S (start symbol)
2. Repeat:
   • If top of stack is variable A: pop A, push RHS of some A → α (nondeterministically)
   • If top of stack is terminal a: read input a, pop a (they must match)
   • If $ on top and input empty: accept

1.2 Worked Example: S → 0S1 | ε

1. (q0, ε, ε) → (q1, $) — init bottom marker
2. (q1, ε, S) → (q1, 1S0) — S → 0S1 (push RHS reversed: 1S0)
3. (q1, ε, S) → (q1, ε) — S → ε
4. (q1, 0, 0) → (q1, ε) — match terminal 0
5. (q1, 1, 1) → (q1, ε) — match terminal 1
6. (q1, ε, $) → (q2, ε) — accept

1.3 Tracing: Input "0011"

2. PDA → CFG Conversion

2.1 Construction

• Variables: [pXq] (state p, pop X, go to state q)
• Start: [q0$qaccept]
• Rules encode transitions For transition δ(p, a, X) = (q, Y1Y2...Yk):
• Add rule: [pXr] → a[qY1r1][r1Y2r2]...[r_{k-1}Yk r]
• For all intermediate states r1, r2, ..., rk

3. Key Concepts Reference

4. 📝 Practice Questions

Q1: Convert S → aSb | ε to a PDA and trace for "ab".

Answer:

Transitions: (q0,ε,ε)→(q1,$), (q1,ε,S)→(q1,bSa), (q1,ε,S)→(q1,ε), (q1,a,a)→(q1,ε), (q1,b,b)→(q1,ε), (q1,ε,$)→(q2,ε)

Trace "ab": Step 0: q0, ab, ε Step 1: q1, ab, $S Step 2: q1, ab,$bSa (S→aSb) Step 3: q1, b, $bS (match a) Step 4: q1, b,$b (S→ε) Step 5: q1, ε, $ (match b) Step 6: q2, ε, ε (accept) Q2: Why must the RHS be pushed in reverse order?

Answer: The stack is LIFO (Last In, First Out). If we have a production A → αβ (where α and β are terminals/variables), we want α to be popped and matched next. Since stack pops from the top, we push β first (deeper in stack), then α (on top). This way α gets processed before β, maintaining derivation order.

5. 🔗 Cross-References

• Week 4 - CFGs: Grammar derivation
• Week 5 - Pushdown Automata: PDA execution
• BSCS4032 (Compiler Design): Parse tree construction Join Discord PreviousContext-Free GrammarsNextPushdown Automata