Equivalence of PDA and CFG

The Big Picture

One of the most important theorems in Theory of Computation!

Theorem: Context-Free Grammars and Pushdown Automata are equivalent

• For every CFG G, there exists a PDA M such that L(G) = N(M)
• For every PDA M, there exists a CFG G such that L(G) = L(M)

Simple Analogy

Think of CFG and PDA like two different maps of the same city:

• CFG: Descriptive map (grammar rules describe how to generate streets)
• PDA: Procedural map (automaton shows how to navigate streets)
• Same city (same language!)
• Different representations (grammar vs automaton)

Why This Matters

Practical implications:

1. Can convert grammar to parser (CFG → PDA)
2. Can infer grammar from automaton (PDA → CFG)
3. Both characterize context-free languages
4. Can choose most convenient representation

Theoretical implications:

1. CFLs have both generative (CFG) and recognitive (PDA) definitions
2. Closure properties proven in either formalism
3. Decision problems solved using either model

Part 1: CFG → PDA

Goal: Given CFG G, construct PDA M such that L(G) = N(M)

Strategy Overview

Key idea: PDA simulates leftmost derivation

Stack contains: Sentential forms (variables and terminals)

Operations:

1. If stack top is variable A, replace with right side of A-production (non-deterministically choose)
2. If stack top is terminal a, match with input and pop
3. Accept when stack empty and input consumed

Formal Construction

Given: CFG G = (V, Σ, R, S)

Construct: PDA M = (Q, Σ, Γ, δ, q₀, S, ∅)

Where:

Q = {q}           (single state!)
Σ = Σ             (same input alphabet)
Γ = V ∪ Σ         (stack alphabet = variables + terminals)
q₀ = q            (start state)
Initial stack: S  (start symbol of grammar)
F = ∅             (accept by empty stack)

Transitions δ:

1. For each production A → α in R:
   δ(q, ε, A) contains (q, α)
   "Replace variable A with right side α"

2. For each terminal a ∈ Σ:
   δ(q, a, a) = {(q, ε)}
   "Match terminal on stack with input"

That’s it! Very simple construction.

Example 1: {aⁿbⁿ}

Grammar G:

S → aSb | ε

Constructed PDA M:

Q = {q}
Σ = {a, b}
Γ = {S, a, b}
Start: q with S on stack
Accept: by empty stack

Transitions:
1. δ(q, ε, S) = {(q, aSb), (q, ε)}
   "Apply S → aSb or S → ε"

2. δ(q, a, a) = {(q, ε)}
   "Match 'a' on stack with input"

3. δ(q, b, b) = {(q, ε)}
   "Match 'b' on stack with input"

Trace for “aabb”

Configuration: (state, input, stack)

(q, aabb, S)         // Start with S on stack
  ⊢ (q, aabb, aSb)   // Apply S → aSb
  ⊢ (q, abb, Sb)     // Match 'a' (pop a from stack)
  ⊢ (q, abb, aSbb)   // Apply S → aSb again
  ⊢ (q, bb, Sbb)     // Match 'a'
  ⊢ (q, bb, bb)      // Apply S → ε (remove S)
  ⊢ (q, b, b)        // Match 'b'
  ⊢ (q, ε, ε)        // Match 'b', ACCEPT! ✓

The PDA simulates the leftmost derivation:

S ⇒ aSb ⇒ aaSbb ⇒ aabb

Example 2: Balanced Parentheses

Grammar G:

S → (S) | SS | ε

Constructed PDA M:

Transitions:
1. δ(q, ε, S) = {(q, (S)), (q, SS), (q, ε)}
   "Three productions for S"

2. δ(q, (, () = {(q, ε)}
   "Match '('"

3. δ(q, ), )) = {(q, ε)}
   "Match ')'"

Trace for ”(())“

(q, (()), S)
  ⊢ (q, (()), (S))    // S → (S)
  ⊢ (q, ()), S)       // Match '('
  ⊢ (q, ()), (S))     // S → (S)
  ⊢ (q, )), S)        // Match '('
  ⊢ (q, )), )         // S → ε
  ⊢ (q, ), ε)         // Match ')'
  ⊢ (q, ε, ε)         // Match ')', ACCEPT! ✓

Why This Works

Correctness:

1. PDA generates what CFG generates:

   • Each derivation S ⇒* w corresponds to accepting computation
   • Stack tracks sentential form during leftmost derivation

2. Non-determinism handles choices:

   • When multiple productions for A, PDA tries all
   • One path succeeds if string is in L(G)

3. Empty stack = completed derivation:

   • All variables replaced (expanded)
   • All terminals matched with input
   • String successfully derived

Important Properties

✓ Single state: Only need one state! ✓ Non-deterministic: Must try all productions ✓ Accept by empty stack: Natural for this construction ✓ Leftmost derivation: Stack simulates leftmost expansion ✓ Time complexity: Exponential in general (non-deterministic)

Part 2: PDA → CFG

Goal: Given PDA M, construct CFG G such that L(M) = L(G)

This is MUCH more complex!

Strategy Overview

Key idea: Variables of CFG represent stack changes in PDA

Variable [p, A, q] means:

• Start in state p with A on top of stack
• End in state q with A popped from stack
• Read some substring of input

Grammar generates: All ways PDA can pop A from stack while going from p to q

Simplification: Empty Stack Acceptance

First: Convert PDA to accept by empty stack

Assume: M = (Q, Σ, Γ, δ, q₀, Z₀, ∅)

Formal Construction

Construct: CFG G = (V, Σ, R, S)

Where:

V = {S} ∪ {[p, A, q] | p, q ∈ Q, A ∈ Γ}
  "Variables represent stack changes"

Σ = Σ
  "Same input alphabet"

S = new start symbol
  "Generates from all possible final states"

R = rules defined below

Production Rules

Rule 1: Start symbol

For each q ∈ Q:
  S → [q₀, Z₀, q]

"Start with q₀ and initial stack, end in any state q"

Rule 2: Pop stack symbol

If δ(p, a, A) contains (r, ε):
  Add production: [p, A, r] → a

"Read 'a', go from p to r, pop A"

Rule 3: Replace stack symbol

If δ(p, a, A) contains (r, B₁B₂...Bₖ):
  For all states q₀, q₁, ..., qₖ:
    Add production: [p, A, qₖ] → a[r, B₁, q₁][q₁, B₂, q₂]...[qₖ₋₁, Bₖ, qₖ]

"Read 'a', replace A with B₁...Bₖ, track how each Bᵢ is eventually popped"

This is complex because we need to track all possible ways stack symbols get popped!

Example 1: Simple PDA

PDA M: Recognizes {aⁿbⁿ}

Q = {q₀, q₁}
Σ = {a, b}
Γ = {A, Z₀}
Accept by empty stack

Transitions:
  δ(q₀, a, Z₀) = {(q₀, AZ₀)}
  δ(q₀, a, A) = {(q₀, AA)}
  δ(q₀, b, A) = {(q₁, ε)}
  δ(q₁, b, A) = {(q₁, ε)}
  δ(q₁, ε, Z₀) = {(q₁, ε)}

Constructed CFG (simplified):

Variables: S, [q₀, Z₀, q₀], [q₀, Z₀, q₁], [q₀, A, q₀], [q₀, A, q₁], [q₁, A, q₁], …

Key productions (showing main derivation path):

S → [q₀, Z₀, q₁]

[q₀, Z₀, q₁] → a[q₀, A, q₁][q₁, Z₀, q₁]
  "From δ(q₀, a, Z₀) = (q₀, AZ₀)"

[q₀, A, q₁] → a[q₀, A, q₁][q₁, A, q₁] | b
  "From δ(q₀, a, A) = (q₀, AA) and δ(q₀, b, A) = (q₁, ε)"

[q₁, A, q₁] → b
  "From δ(q₁, b, A) = (q₁, ε)"

[q₁, Z₀, q₁] → ε
  "From δ(q₁, ε, Z₀) = (q₁, ε)"

Derivation for “aabb” (simplified trace):

S ⇒ [q₀, Z₀, q₁]
  ⇒ a[q₀, A, q₁][q₁, Z₀, q₁]
  ⇒ aa[q₀, A, q₁][q₁, A, q₁][q₁, Z₀, q₁]
  ⇒ aab[q₁, A, q₁][q₁, Z₀, q₁]
  ⇒ aabb[q₁, Z₀, q₁]
  ⇒ aabb

Why This Works (Intuition)

Variable [p, A, q] captures:

• All ways to pop A from stack
• While transitioning from state p to state q
• Reading some input substring

Productions encode:

• Stack operations of PDA
• State transitions
• Input consumption

Grammar derives w iff PDA accepts w

Complexity of Construction

Size of CFG:

• Variables: O(|Q|² × |Γ|)
• Productions: O(|Q|^(k+2) × |δ|) where k = max symbols pushed

For k = 2 (push at most 2 symbols):

• Productions: O(|Q|⁴ × |δ|)

This can be HUGE! But proves equivalence exists.

Example 2: Complete Conversion

PDA for {ww^R}

Given PDA M (simplified):

Q = {q₀, q₁}
Σ = {a, b}
Γ = {A, B, Z₀}

δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, b, Z₀) = {(q₀, BZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
δ(q₀, b, B) = {(q₀, BB)}
δ(q₀, ε, Z₀) = {(q₁, Z₀)}  // Guess middle
δ(q₀, ε, A) = {(q₁, A)}
δ(q₀, ε, B) = {(q₁, B)}
δ(q₁, a, A) = {(q₁, ε)}
δ(q₁, b, B) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₁, ε)}

Constructed CFG (key productions):

S → [q₀, Z₀, q₁]

[q₀, Z₀, q₁] → a[q₀, A, q₁][q₁, Z₀, q₁] | b[q₀, B, q₁][q₁, Z₀, q₁] | ε

[q₀, A, q₁] → a[q₀, A, q₁][q₁, A, q₁] | a

[q₀, B, q₁] → b[q₀, B, q₁][q₁, B, q₁] | b

[q₁, A, q₁] → a
[q₁, B, q₁] → b
[q₁, Z₀, q₁] → ε

This generates {ww^R}!

Proof Sketches

Theorem 1: CFG → PDA

Claim: If L = L(G) for CFG G, then L = N(M) for some PDA M

Proof sketch:

1. Construct M as described (single state, simulate leftmost derivation)
2. Show: w ∈ L(G) ⟺ M accepts w
3. Forward: If S ⇒* w, then (q, w, S) ⊢* (q, ε, ε)
4. Backward: If M accepts w, then S ⇒* w
5. Both proven by induction on derivation length

Theorem 2: PDA → CFG

Claim: If L = N(M) for PDA M, then L = L(G) for some CFG G

Proof sketch:

1. Construct G as described (variables represent stack changes)
2. Show: w ∈ N(M) ⟺ w ∈ L(G)
3. Key lemma: [p, A, q] ⇒* w iff M starting in state p with A on stack (and anything below) accepts w and ends in state q (with same below)
4. Proven by induction on computation length

Important Consequences

Consequence 1: CFL Definition

Three equivalent definitions:

1. L is CFL ⟺ L = L(G) for some CFG G
2. L is CFL ⟺ L = L(M) for some PDA M (final state)
3. L is CFL ⟺ L = N(M) for some PDA M (empty stack)

All are equivalent!

Consequence 2: Closure Properties

Can prove using either CFG or PDA:

• Union: Easy with CFG (S → S₁ | S₂)
• Concatenation: Easy with CFG (S → S₁S₂)
• Kleene star: Easy with CFG (S → SS | ε)

Consequence 3: Decision Problems

Membership problem:

• Given CFG G and string w, is w ∈ L(G)?
• Decidable (CYK algorithm O(n³))
• Could also use PDA simulation

Consequence 4: Parsing

Practical application:

• Write grammar for programming language (CFG)
• Convert to parser (PDA)
• Use in compiler!

Comparison of Conversions

Practical Applications

Application 1: Parser Generation

Workflow:

1. Write CFG for language syntax
2. Convert to PDA (or equivalent)
3. Implement as parser
4. Use in compiler/interpreter

Tools: YACC, Bison, ANTLR

Application 2: Language Design

Benefits:

• CFG: Easy to write and understand
• PDA: Easy to implement
• Equivalence: Can use both!

Application 3: Theoretical Analysis

Use CFG for:

• Closure properties
• Language generation
• Derivation analysis

Use PDA for:

• Recognition algorithms
• Complexity analysis
• Acceptance conditions

Important Exam Points

1. ✓ Equivalence: CFG ≡ PDA (same expressive power)
2. ✓ CFG → PDA: Single state, simulate leftmost derivation
3. ✓ PDA transitions: One per production, one per terminal
4. ✓ PDA → CFG: Variables [p, A, q] represent stack changes
5. ✓ Three definitions: CFG, PDA (final), PDA (empty) all equivalent
6. ✓ Practical: CFG → PDA common (parser generation)
7. ✓ Theoretical: PDA → CFG complex but proves equivalence
8. ✓ Non-determinism: PDA must try all productions
9. ✓ Acceptance: CFG → PDA uses empty stack naturally
10. ✓ Applications: Compiler design, formal language theory

Common Mistakes to Avoid

✗ Mistake 1: Multiple states in CFG → PDA construction
✓ Correct: Only need one state!

✗ Mistake 2: Forgetting to handle ε-productions
✓ Correct: Include δ(q, ε, A) = (q, ε) for A → ε

✗ Mistake 3: Deterministic PDA construction
✓ Correct: Must be non-deterministic to handle multiple productions

✗ Mistake 4: Wrong acceptance mode in CFG → PDA
✓ Correct: Use empty stack (most natural)

✗ Mistake 5: Thinking PDA → CFG is simple
✓ Correct: Complex construction, many productions needed

✗ Mistake 6: Not tracking all possible stack changes
✓ Correct: Variables must cover all state pairs and stack symbols

Practice Questions

Q1: Convert CFG with S → aSb | ε to PDA

Answer:

δ(q, ε, S) = {(q, aSb), (q, ε)}
δ(q, a, a) = {(q, ε)}
δ(q, b, b) = {(q, ε)}

Q2: How many states needed for CFG → PDA?

Answer: One state is sufficient.

Q3: What does variable [p, A, q] represent?

Answer: All ways to pop A from stack while going from state p to q.

Q4: Why is CFG → PDA simpler than PDA → CFG?

Answer: Direct simulation of derivation vs. tracking all stack changes.

Q5: Are CFG and PDA equally powerful?

Answer: Yes, they recognize exactly the context-free languages.

Q6: Can we convert deterministic PDA to CFG?

Answer: Yes, same construction works (DPDA ⊂ CFL).

Q7: Trace (q, ab, S) for PDA from S → aSb | ab

Answer: (q, ab, S) ⊢ (q, ab, ab) ⊢ (q, b, b) ⊢ (q, ε, ε) ✓

Summary

• Equivalence: CFG ≡ PDA (fundamental theorem)
• CFG → PDA: Simple construction (1 state, simulate derivation)
• Transitions: One per production + one per terminal
• Accept by: Empty stack (natural for this direction)
• PDA → CFG: Complex construction (variables track stack changes)
• Variable [p, A, q]: Represents popping A, going p to q
• Productions: Encode PDA transitions and state changes
• Three definitions: All equivalent (CFG, PDA-final, PDA-empty)
• Practical use: CFG → PDA common (parsers)
• Theoretical: Proves CFL characterization
• Applications: Compiler design, language theory
• Key insight: Different representations, same languages

This equivalence is cornerstone of formal language theory and compiler design!