Unit III - Pushdown Automata
Understanding PDA, DPDA, Conversions between CFG and PDA, Pumping Lemma, and CFL Properties
1. Definition of Pushdown Automata (PDA)
A Pushdown Automaton (PDA) is a finite automaton with an additional stack memory. It is used to recognize Context-Free Languages.
Why do we need PDA?
Finite Automata have limited memory (only current state). They cannot handle:
- Counting (like aⁿbⁿ)
- Nested structures (balanced parentheses)
- Matching patterns (palindromes)
Solution: Add a stack for unlimited memory!
Formal Definition:
A PDA is a 7-tuple P = (Q, Σ, Γ, δ, q₀, Z₀, F) where:
- Q: Finite set of states
- Σ: Input alphabet
- Γ: Stack alphabet
- δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*): Transition function
- q₀ ∈ Q: Start state
- Z₀ ∈ Γ: Initial stack symbol
- F ⊆ Q: Set of final states
How PDA Works:
- PDA reads input symbol from left to right
- Based on current state, input symbol, and top stack symbol, it:
- Changes state
- Pops top symbol from stack
- Pushes zero or more symbols onto stack
- Accepts if in final state after reading entire input
Transition Notation:
δ(q, a, X) = {(p, γ)} means:
- In state q
- Reading input a (or ε for no input)
- With X on top of stack
- Move to state p
- Pop X, push string γ (rightmost symbol goes on top)
Example 1: PDA for L = {0ⁿ1ⁿ | n ≥ 0}
Idea: Push 0's onto stack, pop for each 1
| State | Input | Stack Top | Next State | Stack Action |
|---|---|---|---|---|
| q₀ | 0 | Z₀ | q₀ | Push 0 (stack: 0Z₀) |
| q₀ | 0 | 0 | q₀ | Push 0 (stack: 00...) |
| q₀ | 1 | 0 | q₁ | Pop 0 |
| q₁ | 1 | 0 | q₁ | Pop 0 |
| q₁ | ε | Z₀ | q₂ | Accept (empty or Z₀) |
Formal Transitions:
δ(q₀, 0, Z₀) = {(q₀, 0Z₀)}
δ(q₀, 0, 0) = {(q₀, 00)}
δ(q₀, 1, 0) = {(q₁, ε)}
δ(q₁, 1, 0) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₂, Z₀)}
Trace for "0011":
(q₀, 0011, Z₀) ⊢ (q₀, 011, 0Z₀) ⊢ (q₀, 11, 00Z₀)
⊢ (q₁, 1, 0Z₀) ⊢ (q₁, ε, Z₀) ⊢ (q₂, ε, Z₀) [ACCEPT]
Acceptance by PDA:
Two methods:
- Acceptance by Final State: Input is accepted if PDA reaches a final state after consuming entire input (stack can be non-empty)
- Acceptance by Empty Stack: Input is accepted if PDA consumes entire input AND stack becomes empty (no final states needed)
Important Result:
Both acceptance methods are equivalent in power - any language accepted by one method can be accepted by the other.
Instantaneous Description (ID):
Notation: (q, w, γ) represents:
- q: Current state
- w: Remaining input string
- γ: Current stack contents (top at left)
⊢ symbol denotes one move (transition)
⊢* denotes zero or more moves
2. Deterministic Pushdown Automata (DPDA)
A Deterministic PDA (DPDA) has at most one possible transition for each configuration. Unlike regular DFA = NFA equivalence, DPDA is LESS powerful than NPDA!
Conditions for Determinism:
A PDA is deterministic if for every configuration (q, a, X):
- |δ(q, a, X)| ≤ 1: At most one transition
- If δ(q, ε, X) is defined, then δ(q, a, X) must be undefined for all a ∈ Σ
- Cannot have both ε-transition and input-transition from same configuration
Key Differences: DPDA vs NPDA
| Feature | DPDA | NPDA |
|---|---|---|
| Transitions | At most one choice | Multiple choices allowed |
| Acceptance | Usually by final state | By final state or empty stack |
| Languages | Deterministic CFL (DCFL) | All CFL |
| Closure properties | Closed under complement | NOT closed under complement |
| Power | Less powerful | More powerful |
| Examples | LR(k) languages | All CFL (including {wwᴿ}) |
Example: DPDA for L = {aⁿbⁿ | n ≥ 1}
States: q₀ (start), q₁ (reading b's), q₂ (final)
δ(q₀, a, Z₀) = (q₀, AZ₀)
δ(q₀, a, A) = (q₀, AA)
δ(q₀, b, A) = (q₁, ε)
δ(q₁, b, A) = (q₁, ε)
δ(q₁, ε, Z₀) = (q₂, Z₀)
✓ Deterministic: At most one transition per configuration
✓ No conflict between ε and input transitions
Languages NOT Accepted by DPDA:
- L = {wwᴿ | w ∈ {a,b}*}: Even palindromes
- NPDA can guess middle point
- DPDA cannot determine when to switch from pushing to popping
- L = {aⁿbⁿ} ∪ {aⁿb²ⁿ}: Nondeterministic choice needed
Important Result:
DCFL ⊂ CFL (proper subset)
Not every CFL can be recognized by DPDA!
Applications of DPDA:
- Programming Language Parsers: LR(k) parsers are DPDA
- Compiler Design: Deterministic parsing is efficient
- Real-time Systems: Predictable behavior
3. PDA Corresponding to Given CFG
Every Context-Free Grammar can be converted to an equivalent Pushdown Automaton that accepts the same language.
Theorem:
For every CFG G, there exists a PDA P such that L(P) = L(G)
Construction Algorithm (Top-Down Parsing):
- Single State: PDA has only one state q
- Stack: Contains variables and terminals
- Start: Push start symbol S onto stack
- For each production A → α:
- When A is on top of stack, pop A and push α
- δ(q, ε, A) = {(q, α)}
- For each terminal a:
- When a is on top of stack and input is a, pop it
- δ(q, a, a) = {(q, ε)}
- Accept: When stack is empty and input is consumed
Example: Convert CFG to PDA
Grammar:
S → aSb | ε
Language: L = {aⁿbⁿ | n ≥ 0}
PDA Construction:
States: Q = {q}
Stack Alphabet: Γ = {S, a, b, Z₀}
Transitions:
1. δ(q, ε, Z₀) = {(q, SZ₀)} [Push start symbol]
2. δ(q, ε, S) = {(q, aSb), (q, ε)} [Productions for S]
3. δ(q, a, a) = {(q, ε)} [Match terminal a]
4. δ(q, b, b) = {(q, ε)} [Match terminal b]
5. δ(q, ε, Z₀) = {(q, ε)} [Accept]
Trace for "aabb":
(q, aabb, Z₀)
⊢ (q, aabb, SZ₀) [Push S]
⊢ (q, aabb, aSbZ₀) [Use S → aSb]
⊢ (q, abb, SbZ₀) [Match a]
⊢ (q, abb, aSbZ₀) [Use S → aSb]
⊢ (q, bb, SbbZ₀) [Match a]
⊢ (q, bb, bbZ₀) [Use S → ε]
⊢ (q, b, bZ₀) [Match b]
⊢ (q, ε, Z₀) [Match b]
⊢ (q, ε, ε) [Accept]
Another Approach (Bottom-Up Parsing):
Use shift-reduce parsing:
- Shift: Push input symbol onto stack
- Reduce: If top of stack matches right side of production, replace with left side
Important Points:
- The constructed PDA is nondeterministic
- PDA simulates leftmost derivation
- Stack contains sentential form
- Accepts by empty stack
4. CFG Corresponding to a PDA
Every language accepted by a PDA can be generated by a Context-Free Grammar. This proves PDA and CFG have equivalent expressive power.
Theorem:
For every PDA P, there exists a CFG G such that L(G) = L(P)
Construction Algorithm:
Main Idea: Create variables [pXq] representing "path from state p to q that pops X from stack"
- Convert PDA: First convert PDA to accept by empty stack
- Variables: For each pair of states p, q and stack symbol X, create variable [pXq]
- Start Symbol: S → [q₀Z₀qf] for all final states qf
- For each transition: δ(p, a, X) = {(r, Y₁Y₂...Yₖ)}
- Add production: [pXq] → a[rY₁r₁][r₁Y₂r₂]...[rₖ₋₁Yₖq]
- For all possible sequences of states r₁, r₂, ..., rₖ₋₁, q
- If δ(p, a, X) = {(r, ε)}:
- Add production: [pXr] → a
Simplified Example:
PDA for L = {0ⁿ1ⁿ | n ≥ 1}:
Q = {q₀, q₁, q₂}
δ(q₀, 0, Z₀) = {(q₀, 0Z₀)}
δ(q₀, 0, 0) = {(q₀, 00)}
δ(q₀, 1, 0) = {(q₁, ε)}
δ(q₁, 1, 0) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₂, ε)}
Resulting CFG (simplified):
S → [q₀Z₀q₂]
[q₀Z₀q₂] → 0[q₀0q₁][q₁Z₀q₂]
[q₀0q₁] → 0[q₀0q₁] | 1
[q₁Z₀q₂] → ε
Simplification:
S → 0A1
A → 0A1 | ε
Which generates {0ⁿ1ⁿ}
Why This Works:
- Variable [pXq] generates strings that take PDA from state p to q while popping X
- Derivations mirror PDA computations
- Terminal strings correspond to accepting PDA runs
Important Results:
Equivalence of Models:
- PDA (accept by final state) ≡ PDA (accept by empty stack)
- PDA ≡ CFG
- Therefore: CFG = PDA in expressive power
5. Pumping Lemma for Context-Free Languages
The Pumping Lemma for CFLs provides a necessary condition for context-free languages. It's used to prove languages are NOT context-free.
Statement:
If L is a CFL, then there exists a constant n (pumping length) such that:
For any string z ∈ L where |z| ≥ n, z can be divided into five parts z = uvwxy satisfying:
- |vwx| ≤ n: Middle three pieces have bounded length
- |vx| > 0: v and x are not both empty (at least one non-empty)
- ∀i ≥ 0, uvⁱwxⁱy ∈ L: Pumping v and x together keeps string in L
Why Five Parts (not three like Regular Languages)?
- CFGs can have nested structures
- Need to pump on BOTH sides of center
- Example: In aⁿbⁿcⁿdⁿ, pump both a's and d's together
Proof Intuition:
In a parse tree for long string:
- Some variable A must repeat on path from root to leaf
- Can replace subtree to pump or shrink the string
- Maintains context-free structure
Example 1: L = {aⁿbⁿcⁿ | n ≥ 1} is NOT CFL
Proof:
- Assume L is CFL with pumping length n
- Choose z = aⁿbⁿcⁿ, clearly |z| = 3n ≥ n
- By pumping lemma, z = uvwxy where |vwx| ≤ n and |vx| > 0
- Case Analysis:
- Case 1: vwx is in first 2n symbols (contains only a's and b's)
- Then vx contains only a's and/or b's
- Pumping: uv²wx²y will have more a's or b's but same c's
- Not in form aⁿbⁿcⁿ ✗
- Case 2: vwx is in last 2n symbols (contains only b's and c's)
- Then vx contains only b's and/or c's
- Pumping: uv²wx²y will have same a's but more b's or c's
- Not in form aⁿbⁿcⁿ ✗
- Case 3: vwx spans middle (|vwx| ≤ n means it can't contain all three types)
- Similar argument: can't maintain balance of all three
- ✗
- Case 1: vwx is in first 2n symbols (contains only a's and b's)
- Contradiction! Therefore L is NOT context-free
Example 2: L = {aⁿbⁿcⁿdⁿ | n ≥ 1} is NOT CFL
Proof sketch:
- Choose z = aⁿbⁿcⁿdⁿ
- Since |vwx| ≤ n, vwx can span at most 2 different symbol types
- Pumping will increase count of at most 2 types
- Cannot keep all four equal ✗
Example 3: L = {ww | w ∈ {a,b}*} is NOT CFL
Language of doubled strings (like abab, aabbaa)
Proof:
- Choose z = aⁿbaⁿbaⁿbaⁿb
- This is in L (w = aⁿbaⁿb, so z = ww)
- Consider all possible positions for vwx
- Pumping destroys the ww pattern (can verify by cases)
- ✗ NOT CFL
How to Use Pumping Lemma for CFLs:
- Assume L is CFL
- Let n be pumping length
- Choose string z ∈ L cleverly (usually with pattern that must be maintained)
- Consider all possible divisions z = uvwxy with conditions
- Show pumping fails in ALL cases
- Conclude NOT CFL
Common Non-CFL Languages:
- L = {aⁿbⁿcⁿ | n ≥ 0} - Three-way matching
- L = {aⁿ² | n ≥ 0} - Perfect squares
- L = {ww | w ∈ Σ*} - Doubled strings
- L = {aⁿbⁿcⁿdⁿ | n ≥ 0} - Four-way matching
6. Closure Properties of Context-Free Languages
Context-Free Languages have some closure properties but NOT all. This distinguishes them from regular languages.
CFL is CLOSED under:
| Operation | Result | Proof Method |
|---|---|---|
| Union | L₁ ∪ L₂ is CFL | S → S₁ | S₂ (combine grammars) |
| Concatenation | L₁ · L₂ is CFL | S → S₁S₂ |
| Kleene Star | L* is CFL | S → SS₁ | ε |
| Positive Closure | L⁺ is CFL | S → SS₁ | S₁ |
| Reversal | Lᴿ is CFL | Reverse all productions |
| Homomorphism | h(L) is CFL | Replace terminals in grammar |
| Inverse Homomorphism | h⁻¹(L) is CFL | Modify PDA transitions |
Example: Union Closure
L₁ = {aⁿbⁿ | n ≥ 0}: CFG G₁ with S₁ → aS₁b | ε
L₂ = {aⁿb²ⁿ | n ≥ 0}: CFG G₂ with S₂ → aS₂bb | ε
L₁ ∪ L₂: Combined CFG
S → S₁ | S₂
S₁ → aS₁b | ε
S₂ → aS₂bb | ε
CFL is NOT CLOSED under:
| Operation | Result | Counterexample |
|---|---|---|
| Intersection | L₁ ∩ L₂ may not be CFL | L₁ = {aⁿbⁿcᵐ}, L₂ = {aᵐbⁿcⁿ}, L₁ ∩ L₂ = {aⁿbⁿcⁿ} (NOT CFL) |
| Complement | L̄ may not be CFL | Use De Morgan's: L̄₁ ∩ L̄₂ = (L₁ ∪ L₂)̄ |
| Difference | L₁ - L₂ may not be CFL | L₁ - L₂ = L₁ ∩ L̄₂ |
Special Case - Intersection with Regular Language:
If L is CFL and R is Regular, then L ∩ R is CFL
Proof: Run PDA and DFA in parallel (product construction)
Practical Implications:
- Cannot use complement to simplify CFL problems
- Must be careful combining CFLs with intersection
- Can intersect with regular language (useful for filtering)
7. Decision Problems Involving Context-Free Languages
Decision Problems are questions about languages that have yes/no answers. Some are decidable (algorithm exists), others are undecidable.
DECIDABLE Problems for CFLs:
| Problem | Question | Algorithm | Complexity |
|---|---|---|---|
| Membership | Is w ∈ L(G)? | CYK parsing algorithm | O(n³) |
| Emptiness | Is L(G) = ∅? | Check if start symbol is generating | O(n) |
| Finiteness | Is L(G) finite? | Check for cycles in reduced grammar | Polynomial |
1. Membership Problem:
Question: Given CFG G and string w, is w ∈ L(G)?
Algorithm: CYK (Cocke-Younger-Kasami) Algorithm
- Requires grammar in Chomsky Normal Form
- Uses dynamic programming
- Builds table of possible derivations
- Time: O(n³|G|) where n = |w|
CYK Algorithm Outline:
- Convert grammar to CNF
- Create table T[i,j] = variables that derive substring w[i...j]
- Fill table bottom-up:
- Base: T[i,i] = {A | A → wᵢ}
- Recursive: T[i,j] = {A | A → BC, B ∈ T[i,k], C ∈ T[k+1,j]}
- Accept if S ∈ T[1,n]
2. Emptiness Problem:
Question: Is L(G) = ∅?
Algorithm:
- Find all generating variables (variables that derive terminal strings)
- Check if start symbol S is generating
- L(G) = ∅ if and only if S is not generating
3. Finiteness Problem:
Question: Is L(G) finite or infinite?
Algorithm:
- Simplify grammar (remove useless symbols)
- Check for cycles: variable A such that A ⇒⁺ αAβ
- L(G) is infinite if and only if there's a useful cycle
UNDECIDABLE Problems for CFLs:
| Problem | Question | Status |
|---|---|---|
| Equivalence | Is L(G₁) = L(G₂)? | UNDECIDABLE |
| Universality | Is L(G) = Σ*? | UNDECIDABLE |
| Intersection Non-Empty | Is L(G₁) ∩ L(G₂) ≠ ∅? | UNDECIDABLE |
| Inclusion | Is L(G₁) ⊆ L(G₂)? | UNDECIDABLE |
| Ambiguity | Is G ambiguous? | UNDECIDABLE |
| CFL Test | Is L(G) context-free? | Trivially YES (G is CFG) |
| Regular Test | Is L(G) regular? | UNDECIDABLE |
Why Some Problems are Undecidable:
- CFLs are complex enough to encode computation
- Can reduce Turing Machine halting problem to these
- No algorithm can solve them for all inputs
Comparison with Regular Languages:
| Problem | Regular Languages | Context-Free Languages |
|---|---|---|
| Membership | Decidable (O(n)) | Decidable (O(n³)) |
| Emptiness | Decidable | Decidable |
| Finiteness | Decidable | Decidable |
| Equivalence | Decidable | UNDECIDABLE |
| Universality | Decidable | UNDECIDABLE |
Summary:
Decidable: Membership, Emptiness, Finiteness
Undecidable: Equivalence, Universality, Ambiguity, Inclusion, Intersection emptiness
⚡ Quick Revision (Unit III Cheat Sheet)
PDA Core
- PDA: (Q, Σ, Γ, δ, q₀, Z₀, F), δ(q,a,X) ⊆ Q × Γ*.
- Accept: By final state OR empty stack (equivalent).
- CFG ≡ PDA: Every CFL has PDA; conversion via leftmost derivation simulation.
DPDA vs NPDA
- DPDA: At most one transition; no simultaneous ε & input moves; recognizes DCFL.
- NPDA: May branch; recognizes all CFL. Proper inclusion: DCFL ⊂ CFL.
Pumping Lemma (CFL)
For |z| ≥ n: z = uvwxy, |vwx| ≤ n, |vx| > 0, ∀i ≥ 0 uvⁱwxⁱy ∈ L. Use for NOT CFL proofs (e.g., aⁿbⁿcⁿ).
Closure CFL
Closed: union, concat, star, homomorphism, inverse homomorphism, reversal, intersection with Regular. Not closed: intersection, complement, difference.
Decidable for CFG
- Membership (CYK O(n³)), Emptiness, Finiteness.
- Undecidable: Equivalence, Universality, Ambiguity, Inclusion, Intersection non-empty.