Pushdown_Automata

Pushdown Automata (PDA) – Complete Exam Notes

Pushdown Automata (PDA) – Complete Exam Preparation

Full Notes with Examples, Conversions, Pumping Lemma & Exam Tips

1. Pushdown Automaton – Definition

A Pushdown Automaton (PDA) is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

ComponentMeaning
QFinite set of states
ΣInput alphabet
ΓStack alphabet (Γ ⊃ Σ usually)
δTransition function: Q × (Σ ∪ {ε}) × Γ → finite set of (Q × Γ*)
q₀Initial state
Z₀Initial stack symbol (usually Z or $)
F ⊆ QSet of final (accepting) states

Two Types of Acceptance

TypeAcceptance ByMost Common in Exams
Acceptance by Final StateEnd in q ∈ F (stack may have garbage)Yes
Acceptance by Empty StackStack becomes empty (state doesn't matter)Yes
Both are equivalent in power → recognize exactly Context-Free Languages

2. Instantaneous Description (ID)

Represented as: (current state, remaining input, current stack)
Example: (q₁, 0011, AZB)

3. Important PDA Designs (Must Know)

1. PDA for { aⁿ bⁿ | n ≥ 0 } (Classic)
Idea: Push a on stack for each a, pop a for each b
δ(q0, a, Z) = (q0, aZ)        → push a
δ(q0, a, a) = (q0, aa)        → push a
δ(q0, ε, Z) = (q1, Z)         → move to q1
δ(q1, b, a) = (q1, ε)         → pop a
δ(q1, ε, Z) = (qf, Z)         → accept (final state)
2. PDA for { wwʳ | w ∈ {a,b}* } (Palindromes)
Phase 1: Push all input
Phase 2: After nondeterministic ε-move, start matching reverse
δ(q0, a, Z) = (q0, aZ),   δ(q0, b, Z) = (q0, bZ)
δ(q0, ε, Z) = (q1, Z)                 → guess middle
δ(q1, a, a) = (q1, ε),   δ(q1, b, b) = (q1, ε)
Accept by empty stack
3. PDA for Even-length palindromes
Same as above but reject odd length by requiring center symbol.

4. Equivalence: CFG ↔ PDA (Most Important Theorem)

Theorem: A language is Context-Free ⇔ it is accepted by a PDA
→ L(PDA) = L(CFG)

Conversions (Frequently Asked)

ConversionMethodDifficulty
CFG → PDAStandard construction (push RHS, pop LHS)Medium
PDA → CFGUsing variables [q X p] meaning "go from q to p popping X at top"Hard (10–15 marks)

Standard CFG → PDA Construction (Remember Steps)

  1. Start: (q₀, ε, S$) → (q, ε, RHS$)
  2. For terminal: (q, a, a) → (q, ε, ε)
  3. For variable: (q, ε, A) → (q, ε, RHS)
  4. Accept by empty stack

5. Deterministic vs Non-deterministic PDA

TypePowerExamples of Languages NOT Accepted by DPDA
DPDAProper subset of CFL{wwʳ} is NOT accepted by DPDA (needs nondeterminism to guess middle)
NPDAll CFLs—

6. Pumping Lemma for Context-Free Languages (Killer Question)

CFL Pumping Lemma:
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

How to Prove Language is NOT CFL

  1. Assume L is CFL → ∃ p
  2. Choose smart w (usually aᵖ bᵖ cᵖ dᵖ or aᵖ bᵖ aᵖ bᵖ)
  3. Show that for some k (usually k=0 or k=2), uvᵏxyᵏz ∉ L
Prove {aⁿ bⁿ cⁿ | n ≥ 0} is NOT CFL
Let w = aᵖ bᵖ cᵖ
w = uvxyz, |vxy| ≤ p, |vy| ≥ 1
→ vxy can cover at most 2 symbols
→ pumping k=2 → one symbol gets more count → not equal → contradiction

7. Closure Properties of CFLs (Important)

OperationClosed?Counterexample if No
UnionYes—
ConcatenationYes—
Kleene StarYes—
IntersectionNo{aⁿbⁿcⁿ} = {aⁿbⁿ} ∩ {bⁿcⁿ}
ComplementNo—
DifferenceNo—
Intersection with RegularYes—

8. Most Important Exam Questions – Unit IV

  1. Design PDA for {aⁿbⁿ}, {wwʳ}, {aⁿb²ⁿ}, equal number of a,b,c etc. (8–12 marks)
  2. Convert given CFG to PDA (step-by-step)
  3. Prove given language is not CFL using Pumping Lemma (aⁿbⁿcⁿ, aᵐbⁿcᵐdⁿ)
  4. Show two PDAs are equivalent
  5. Difference between DPDA and NPDA
  6. Prove closure properties with examples
  7. Construct PDA accepting by final state vs empty stack

Quick Revision One-Liners

  • PDA = FA + One Stack → Context-Free
  • wwʳ needs nondeterminism → not accepted by DPDA
  • CFLs not closed under intersection → hence not complement
  • Pumping: uvᵏxyᵏz must stay in language
  • Always choose w with p exponents
  • Stack is LIFO → perfect for matching parentheses, nested structures
Back to TUFL