Unit IV: Pushdown Automata
Unit IV: Pushdown Automata & Properties of Context-Free Languages
Complete Exam-Oriented Notes with Examples, Theorems & High-Weightage Questions
1. Pushdown Automata – Formal Definition
A Pushdown Automaton (PDA) is a 7-tuple:
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
- Q → finite states
- Σ → input alphabet
- Γ → stack alphabet
- δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ* (nondeterministic)
- q₀ → start state
- Z₀ → initial stack symbol
- F → set of accepting states
2. Types of Acceptance
| Type | Acceptance Condition | Equally Powerful? |
|---|---|---|
| By Final State | Reach any state in F | YES → both recognize exactly CFLs |
| By Empty Stack | Stack becomes empty |
3. NPDA vs DPDA (Very Important)
| Feature | NPDA | DPDA |
|---|---|---|
| Transition function | May have multiple or ε-moves | Exactly one move for every (state, input/ε, top) |
| Power | All Context-Free Languages | Only Deterministic CFLs (DCFLs) |
| Examples of languages NOT in DCFL | — | {wwʳ | w ∈ {a,b}*} (needs to guess center) |
{wwʳ} is CFL but NOT deterministic → requires nondeterminism to guess the middle
4. Classic PDA Constructions (Must Know)
PDA for L = {aⁿ bⁿ | n ≥ 0}
Push A for each a → pop A for each b
Accept by empty stack or final state
Push A for each a → pop A for each b
Accept by empty stack or final state
PDA for Palindromes {wwʳ | w ∈ {a,b}*}
Phase 1: Nondeterministically push all symbols
Phase 2: After guessing middle (ε-move), start popping and matching
→ This is nondeterministic → no DPDA exists
Phase 1: Nondeterministically push all symbols
Phase 2: After guessing middle (ε-move), start popping and matching
→ This is nondeterministic → no DPDA exists
PDA for {aⁿ bᵐ cⁿ⁺ᵐ}
Push A for a, push B for b → pop with c → works with one stack
Push A for a, push B for b → pop with c → works with one stack
5. Equivalence Results (High Weightage)
Theorem 1: A language is Context-Free ⇔ Accepted by a PDA ⇔ Generated by a CFG
Theorem 2: NPDA ≡ CFG in power
DPDA recognizes only a proper subset (DCFLs)
DPDA recognizes only a proper subset (DCFLs)
6. Two-Stack PDA = Turing Machine
A PDA with TWO stacks has the same power as a Turing Machine → can recognize any recursively enumerable language
Proof idea: Simulate TM tape using two stacks (left and right parts)
7. Pumping Lemma for Context-Free Languages (Killer Question)
If L is CFL, then ∃ p such that ∀ w ∈ L with |w| ≥ p,
w = uvxyz such that:
1. |vxy| ≤ p
2. |vy| ≥ 1
3. ∀ k ≥ 0, uvᵏ x yᵏ z ∈ L
w = uvxyz such that:
1. |vxy| ≤ p
2. |vy| ≥ 1
3. ∀ k ≥ 0, uvᵏ x yᵏ z ∈ L
Prove {aⁿ bⁿ cⁿ | n ≥ 0} is NOT CFL
Take w = aᵖ bᵖ cᵖ
vxy can cover at most two symbols → pumping up (k=2) increases only two counters → cannot maintain equality of all three → contradiction
Take w = aᵖ bᵖ cᵖ
vxy can cover at most two symbols → pumping up (k=2) increases only two counters → cannot maintain equality of all three → contradiction
8. Closure Properties of CFLs (Most Asked)
| Operation | Closed? | Counterexample if No |
|---|---|---|
| Union | Yes | — |
| Concatenation | Yes | — |
| Kleene Star | Yes | — |
| Intersection | No | {aⁿbⁿcⁿ} = {aⁿbⁿ} ∩ {bⁿcⁿ} |
| Complement | No | If closed, intersection would be closed (De Morgan) |
| Difference | No | — |
| Intersection with Regular | Yes | — |
| Homomorphism | Yes | — |
9. Decision Problems for CFLs
| Problem | Decidable? | Remarks |
|---|---|---|
| Membership | Yes | CYK algorithm |
| Emptiness | Yes | Check if S generates terminal string |
| Finiteness | Yes | Check for self-embedding |
| Equivalence | No | Undecidable for CFLs |
| Is L regular? | No | Undecidable |
10. Most Important Exam Questions (Repeated Every Year)
- Design NPDA for {aⁿ bᵐ cⁿ⁺ᵐ}, {wwʳ}, equal number of a,b,c etc. (10–12 marks)
- Prove that {wwʳ} is not accepted by any DPDA
- Prove a given language is not CFL using Pumping Lemma (aⁿbⁿcⁿ, aⁿbᵐcⁿdᵐ etc.)
- Show that CFLs are not closed under intersection/complement
- Explain why two-stack PDA = Turing Machine
- Convert given CFG → PDA and vice-versa
- State and prove closure properties of CFLs
- Decision algorithms/table for CFLs vs Regular languages
Quick Revision One-Liners
- PDA + Nondeterminism → All CFLs
- DPDA → Only DCFLs (proper subset)
- wwʳ requires guessing middle → not deterministic
- CFLs closed under union, concat, star → NOT intersection/complement
- Two stacks → full Turing power
- Pumping: uvᵏxyᵏz must stay in language
- Always pick w = aᵖ bᵖ cᵖ … for pumping lemma