PDA Formal Definition (Detailed)
Pushdown Automaton (PDA) is formally defined as a 7-tuple:
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
Component Breakdown
1. Q - Set of States
Definition: Finite set of control states
Example:
Q = {q₀, q₁, q₂, qaccept}Think: Like states in finite automaton, but with stack access
2. Σ - Input Alphabet
Definition: Finite set of input symbols
Example:
Σ = {a, b, c}
Σ = {0, 1}
Σ = {(, ), [, ]}Note: Same as DFA/NFA input alphabet
3. Γ - Stack Alphabet
Definition: Finite set of stack symbols
Example:
Γ = {A, B, Z₀}
Γ = {0, 1, $}Important: Γ can be different from Σ!
Common convention: Z₀ represents initial stack symbol (bottom marker)
4. δ - Transition Function
Most complex component!
Signature:
δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)Breakdown:
- Input: (currentstate, input_symbol_orε, top_of_stack)
- Output: Set of (new_state, string_to_push)
Example Transitions:
δ(q₀, a, Z₀) = {(q₁, AZ₀)}
"In state q₀, reading 'a', stack top Z₀
→ go to q₁, push A (Z₀ stays below)"
δ(q₁, b, A) = {(q₁, ε)}
"In state q₁, reading 'b', stack top A
→ stay in q₁, pop A (push nothing)"
δ(q₀, ε, A) = {(q₁, AA), (q₂, ε)}
"Non-deterministic: without reading input,
can either push A or pop A"Key Points:
- Can have multiple transitions (non-determinism)
- ε means no input consumed
- ε on stack means pop without push
- String on right means push multiple symbols
5. q₀ - Start State
Definition: Initial state (q₀ ∈ Q)
Example: q₀, qstart, s₀
Always: Computation begins here
6. Z₀ - Initial Stack Symbol
Definition: Symbol at bottom of stack initially (Z₀ ∈ Γ)
Purpose:
- Marks bottom of stack
- Helps detect empty stack
- Never disappears (usually)
Common names: Z₀, $, ⊥
7. F - Final States
Definition: Set of accepting states (F ⊆ Q)
Example:
F = {qaccept}
F = {q₂, q₃}
F = ∅ (if accepting by empty stack)Note: Used for “acceptance by final state” mode
Configuration and Moves
Instantaneous Description (ID)
Configuration of PDA at any point:
(q, w, α)
Where:
- q ∈ Q: current state
- w ∈ Σ*: remaining input string
- α ∈ Γ*: current stack contents (top first)
Example:
(q₀, aabb, Z₀) // Start: state q₀, input "aabb", stack [Z₀]
(q₁, abb, AZ₀) // After one move
(q₁, bb, AAZ₀) // After two movesMove Relation (⊢)
Notation: (q, aw, Xβ) ⊢ (p, w, αβ)
Meaning: One step of computation
- From state q, reading input ‘a’, stack top X
- To state p, consumed ‘a’, replaced X with α
- β remains on stack below
Formally: If δ(q, a, X) contains (p, α), then:
(q, aw, Xβ) ⊢ (p, w, αβ)Example:
If δ(q₀, a, Z₀) = {(q₁, AZ₀)}, then:
(q₀, aabb, Z₀) ⊢ (q₁, abb, AZ₀)Multi-Step Moves
⊢* : Reflexive transitive closure (zero or more moves) ⊢⁺ : Transitive closure (one or more moves)
Example:
(q₀, aabb, Z₀) ⊢* (q₂, ε, Z₀)
"Can reach (q₂, ε, Z₀) from (q₀, aabb, Z₀) in zero or more steps"Example 1: {aⁿbⁿ | n ≥ 1} - Detailed Walkthrough
Language: {ab, aabb, aaabbb, …}
PDA Design
Formal Definition:
Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {A, Z₀}
q₀ = q₀
Z₀ = Z₀
F = {q₂}Transitions:
1. δ(q₀, a, Z₀) = {(q₀, AZ₀)} // First 'a': push A
2. δ(q₀, a, A) = {(q₀, AA)} // More 'a's: push A
3. δ(q₀, b, A) = {(q₁, ε)} // First 'b': pop A, switch state
4. δ(q₁, b, A) = {(q₁, ε)} // More 'b's: pop A
5. δ(q₁, ε, Z₀) = {(q₂, Z₀)} // Done: go to final stateState Diagram
[q₀] --a,Z₀/AZ₀--> (q₀)
| ^
| |
| a,A/AA
|
+----b,A/ε-----> [q₁]
|
b,A/ε
|
v
ε,Z₀/Z₀
|
v
((q₂))Legend: state —input,stack_top/push—> next_state
Complete Trace for “aabb”
Step-by-step:
Step 0: (q₀, aabb, Z₀)
State: q₀
Input: aabb
Stack: [Z₀]
Action: Read 'a', δ(q₀, a, Z₀) = (q₀, AZ₀)
Step 1: (q₀, abb, AZ₀)
State: q₀
Input: abb
Stack: [A, Z₀] (A on top)
Action: Read 'a', δ(q₀, a, A) = (q₀, AA)
Step 2: (q₀, bb, AAZ₀)
State: q₀
Input: bb
Stack: [A, A, Z₀]
Action: Read 'b', δ(q₀, b, A) = (q₁, ε)
Step 3: (q₁, b, AZ₀)
State: q₁
Input: b
Stack: [A, Z₀] (popped one A)
Action: Read 'b', δ(q₁, b, A) = (q₁, ε)
Step 4: (q₁, ε, Z₀)
State: q₁
Input: ε (all consumed)
Stack: [Z₀] (popped second A)
Action: ε-transition, δ(q₁, ε, Z₀) = (q₂, Z₀)
Step 5: (q₂, ε, Z₀)
State: q₂ ∈ F ✓ (final state)
Input: ε ✓ (all consumed)
Stack: [Z₀]
ACCEPT! ✓Trace for “aaab” (Rejected)
Step 0: (q₀, aaab, Z₀)
Step 1: (q₀, aab, AZ₀) // Push A
Step 2: (q₀, ab, AAZ₀) // Push A
Step 3: (q₀, b, AAAZ₀) // Push A
Step 4: (q₁, ε, AAZ₀) // Pop A for 'b'
// Now: Input exhausted but stack still has AA
// Can't reach final state with remaining stack
// REJECT! ✗Why This Works
Invariant: Number of A’s on stack = unmatched ‘a’s
Phases:
- Push phase: Count ‘a’s by pushing
- Pop phase: Match ‘b’s by popping
- Accept: If counts match (stack empty except Z₀)
Example 2: {ww^R | w ∈ {a,b}*} - Palindromes
Language: Even-length palindromes {aa, bb, abba, baab, aabbaa, …}
PDA Design
Formal Definition:
Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {A, B, Z₀}
Start: q₀
Initial stack: Z₀
Final: {q₂}Key Idea: Non-deterministically guess the middle!
Transitions:
// Phase 1: Push symbols
1. δ(q₀, a, Z₀) = {(q₀, AZ₀)}
2. δ(q₀, a, A) = {(q₀, AA)}
3. δ(q₀, a, B) = {(q₀, AB)}
4. δ(q₀, b, Z₀) = {(q₀, BZ₀)}
5. δ(q₀, b, A) = {(q₀, BA)}
6. δ(q₀, b, B) = {(q₀, BB)}
// Phase 2: Guess middle (ε-transition)
7. δ(q₀, ε, Z₀) = {(q₁, Z₀)}
8. δ(q₀, ε, A) = {(q₁, A)}
9. δ(q₀, ε, B) = {(q₁, B)}
// Phase 3: Match and pop
10. δ(q₁, a, A) = {(q₁, ε)} // 'a' matches A
11. δ(q₁, b, B) = {(q₁, ε)} // 'b' matches B
12. δ(q₁, ε, Z₀) = {(q₂, Z₀)} // AcceptTrace for “abba”
Non-deterministic exploration:
(q₀, abba, Z₀)
/ \
Push 'a' Guess middle (wrong!)
| |
(q₀, bba, AZ₀) (q₁, abba, Z₀)
/ \ |
Push Guess Try to match...
| | ✗ Fails!
Continue Try
...
Correct path:
(q₀, abba, Z₀)
⊢ (q₀, bba, AZ₀) // Push A for 'a'
⊢ (q₀, ba, BAZ₀) // Push B for 'b'
⊢ (q₁, ba, BAZ₀) // Guess middle (ε-transition)
⊢ (q₁, a, AZ₀) // Match 'b' with B, pop
⊢ (q₁, ε, Z₀) // Match 'a' with A, pop
⊢ (q₂, ε, Z₀) // Accept!
✓ ACCEPTKey: PDA explores all possible middle points; accepts if any succeeds!
Example 3: Balanced Parentheses
Language: {ε, (), (()), ()(), (())(), …}
PDA Design
Q = {q₀, qf}
Σ = {(, )}
Γ = {X, Z₀}
Start: q₀
Initial: Z₀
Final: {qf}Transitions:
1. δ(q₀, (, Z₀) = {(q₀, XZ₀)} // First '(': push X
2. δ(q₀, (, X) = {(q₀, XX)} // More '(': push X
3. δ(q₀, ), X) = {(q₀, ε)} // ')': pop X
4. δ(q₀, ε, Z₀) = {(qf, Z₀)} // Accept if balancedTrace for ”(())“
(q₀, (()), Z₀)
⊢ (q₀, ()), XZ₀) // Push X for '('
⊢ (q₀, )), XXZ₀) // Push X for '('
⊢ (q₀, ), XZ₀) // Pop X for ')'
⊢ (q₀, ε, Z₀) // Pop X for ')'
⊢ (qf, ε, Z₀) // Accept!
✓Trace for ”(()” (Rejected)
(q₀, ((), Z₀)
⊢ (q₀, (), XZ₀)
⊢ (q₀, ), XXZ₀)
⊢ (q₀, ε, XZ₀) // Input exhausted, but stack not empty!
✗ Can't reach final stateExample 4: {aⁿbⁿcᵐdᵐ | n,m ≥ 1}
Language: ab, aabbcd, aaabbbcccddd, …
Two independent counts!
PDA Design
Q = {q₀, q₁, q₂, q₃}
Σ = {a, b, c, d}
Γ = {A, C, Z₀}Transitions:
// Phase 1: Count a's
δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
// Phase 2: Match b's
δ(q₀, b, A) = {(q₁, ε)}
δ(q₁, b, A) = {(q₁, ε)}
// Phase 3: Count c's
δ(q₁, c, Z₀) = {(q₂, CZ₀)}
δ(q₂, c, C) = {(q₂, CC)}
// Phase 4: Match d's
δ(q₂, d, C) = {(q₃, ε)}
δ(q₃, d, C) = {(q₃, ε)}
// Accept
δ(q₃, ε, Z₀) = {(qf, Z₀)}Trace for “aabbcd”
(q₀, aabbcd, Z₀)
⊢ (q₀, abbcd, AZ₀) // Push A
⊢ (q₀, bbcd, AAZ₀) // Push A
⊢ (q₁, bcd, AZ₀) // Pop A for 'b'
⊢ (q₁, cd, Z₀) // Pop A for 'b'
⊢ (q₂, d, CZ₀) // Push C for 'c'
⊢ (q₃, ε, Z₀) // Pop C for 'd'
⊢ (qf, ε, Z₀) // Accept!
✓Why this works: Stack can count two values sequentially (not simultaneously)
Example 5: {aⁿb²ⁿ | n ≥ 1}
Language: abb, aabbbb, aaabbbbbb, …
Each ‘a’ matched by two ‘b’s!
PDA Design
Q = {q₀, q₁}
Σ = {a, b}
Γ = {A, Z₀}Transitions:
δ(q₀, a, Z₀) = {(q₀, AAZ₀)} // Push TWO A's for each 'a'
δ(q₀, a, A) = {(q₀, AAA)} // Push TWO A's
δ(q₀, b, A) = {(q₁, ε)} // Pop one A for 'b'
δ(q₁, b, A) = {(q₁, ε)} // Pop one A for 'b'
δ(q₁, ε, Z₀) = {(qf, Z₀)} // AcceptTrace for “aabbbb”
(q₀, aabbbb, Z₀)
⊢ (q₀, abbbb, AAAZ₀) // Push 2 A's for first 'a'
⊢ (q₀, bbbb, AAAAAZ₀) // Push 2 A's for second 'a'
⊢ (q₁, bbb, AAAAZ₀) // Pop A for 'b'
⊢ (q₁, bb, AAAZ₀) // Pop A for 'b'
⊢ (q₁, b, AAZ₀) // Pop A for 'b'
⊢ (q₁, ε, AZ₀) // Pop A for 'b'
// Wait, stack still has A! Should continue...Let me fix the trace:
(q₀, aabbbb, Z₀)
⊢ (q₀, abbbb, AAZ₀) // Push 2 A's for 'a'
⊢ (q₀, bbbb, AAAAZ₀) // Push 2 A's for 'a'
⊢ (q₁, bbb, AAAZ₀) // Pop A
⊢ (q₁, bb, AAZ₀) // Pop A
⊢ (q₁, b, AZ₀) // Pop A
⊢ (q₁, ε, Z₀) // Pop A
⊢ (qf, ε, Z₀) // Accept!
✓Example 6: {w ∈ {a,b}* | nₐ(w) = n_b(w)}
Language: Equal number of a’s and b’s (any order)
Examples: ab, ba, aabb, abab, baba, …
PDA Design
Challenge: Can’t predict order!
Solution: Stack tracks difference between counts
Q = {q₀, qf}
Σ = {a, b}
Γ = {A, B, Z₀}Transitions:
// 'a' when stack has 'b' (cancel out)
δ(q₀, a, B) = {(q₀, ε)}
// 'a' when no 'b' (push)
δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
// 'b' when stack has 'a' (cancel out)
δ(q₀, b, A) = {(q₀, ε)}
// 'b' when no 'a' (push)
δ(q₀, b, Z₀) = {(q₀, BZ₀)}
δ(q₀, b, B) = {(q₀, BB)}
// Accept if equal
δ(q₀, ε, Z₀) = {(qf, Z₀)}Trace for “abba”
(q₀, abba, Z₀)
⊢ (q₀, bba, AZ₀) // Push A for 'a'
⊢ (q₀, ba, Z₀) // Pop A (canceled by 'b')
⊢ (q₀, a, BZ₀) // Push B for 'b'
⊢ (q₀, ε, Z₀) // Pop B (canceled by 'a')
⊢ (qf, ε, Z₀) // Accept!
✓Example 7: {w#w^R | w ∈ {a,b}*}
Language: Palindromes with center marker
Examples: #, a#a, ab#ba, aabb#bbaa
PDA Design
Advantage: ’#’ marks middle explicitly (no guessing!)
Q = {q₀, q₁, q₂}
Σ = {a, b, #}
Γ = {A, B, Z₀}Transitions:
// Phase 1: Push before '#'
δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
δ(q₀, a, B) = {(q₀, AB)}
δ(q₀, b, Z₀) = {(q₀, BZ₀)}
δ(q₀, b, A) = {(q₀, BA)}
δ(q₀, b, B) = {(q₀, BB)}
// Phase 2: See '#', switch state
δ(q₀, #, Z₀) = {(q₁, Z₀)}
δ(q₀, #, A) = {(q₁, A)}
δ(q₀, #, B) = {(q₁, B)}
// Phase 3: Match after '#'
δ(q₁, a, A) = {(q₁, ε)}
δ(q₁, b, B) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₂, Z₀)}Deterministic! (No guessing needed because of ’#‘)
Important Design Patterns
Pattern 1: Counting
Use: {aⁿbⁿ}, {aⁿbⁿcᵐdᵐ}
Strategy: Push for first, pop for second
Pattern 2: Matching
Use: Balanced parentheses, XML tags
Strategy: Stack stores unmatched opening symbols
Pattern 3: Guessing
Use: {ww^R} (no center marker)
Strategy: Non-deterministically guess middle point
Pattern 4: Cancellation
Use: {w | nₐ(w) = n_b(w)}
Strategy: Push/pop based on difference
Pattern 5: Multiple Phases
Use: {aⁿbⁿcᵐdᵐ}
Strategy: Sequential counting using same stack
Common Exam Problems
Q1: Design PDA for {aⁿbⁿ | n ≥ 0}
Solution: Like Example 1, but allow ε (add δ(q₀, ε, Z₀) = {(qf, Z₀)})
Q2: Design PDA for {wcw^R | w ∈ {a,b}*}
Solution: Like Example 7 (use ‘c’ as center marker)
Q3: Design PDA for {aⁿbᵐ | n ≤ m ≤ 2n}
Solution: Complex! Push A’s for a’s, pop 1 or 2 A’s per b non-deterministically
Q4: Design PDA for {aⁱbʲcᵏ | i = j or j = k}
Solution: Non-deterministically choose which equality to enforce
Important Exam Points
- ✓ 7-tuple: (Q, Σ, Γ, δ, q₀, Z₀, F)
- ✓ Configuration: (state, remaining_input, stack_contents)
- ✓ Move: (q, aw, Xβ) ⊢ (p, w, αβ) if δ(q,a,X) contains (p,α)
- ✓ Non-determinism: Multiple transitions, ε-transitions, guessing
- ✓ Stack operations: Push (add to top), Pop (remove from top)
- ✓ Design patterns: Counting, matching, guessing, cancellation
- ✓ Sequential counting: Can handle aⁿbⁿcᵐdᵐ but not aⁿbⁿcⁿ
- ✓ Center marker: Makes palindromes deterministic (w#w^R)
- ✓ Trace: Show complete sequence of configurations
- ✓ Acceptance: Depends on mode (final state or empty stack)
Common Mistakes to Avoid
✗ Mistake 1: Trying to recognize {aⁿbⁿcⁿ}
✓ Correct: Impossible with one stack (need two counters)
✗ Mistake 2: Forgetting Z₀ in transitions
✓ Correct: Always specify what’s on stack top
✗ Mistake 3: Wrong push order
✓ Correct: δ(q,a,X) = (p,ABC) pushes C, then B, then A (A on top)
✗ Mistake 4: Not showing all configurations in trace
✓ Correct: Show every intermediate step
✗ Mistake 5: Confusing input and stack alphabets
✓ Correct: Σ (input) and Γ (stack) can be different
✗ Mistake 6: Accessing bottom of stack
✓ Correct: Only top is accessible
Practice Questions
Q1: What does δ(q₀, a, Z₀) = {(q₁, AZ₀), (q₂, ε)} represent?
Answer: Non-deterministic choice: read ‘a’, either push A or pop Z₀.
Q2: Trace (q₀, ab, Z₀) for {aⁿbⁿ} PDA
Answer: (q₀,ab,Z₀) ⊢ (q₀,b,AZ₀) ⊢ (q₁,ε,Z₀) ⊢ (q₂,ε,Z₀) ✓
Q3: Can PDA recognize {aⁿbⁿcⁿ}?
Answer: No, needs two independent counters (only have one stack).
Q4: What makes {ww^R} need non-determinism?
Answer: Must guess where middle is (no marker).
Q5: How is {w#w^R} different from {ww^R}?
Answer: ’#’ marks middle explicitly, so deterministic.
Summary
- PDA: 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F)
- Configuration: (state, input, stack)
- Transition: δ(state, input, stack_top) = {(new_state, push_symbols)}
- Move: One step of computation
- Non-determinism: Multiple transitions, guessing
- Design patterns: Counting, matching, guessing, cancellation
- Can handle: {aⁿbⁿ}, {ww^R}, balanced parentheses, {aⁿbⁿcᵐdᵐ}
- Cannot handle: {aⁿbⁿcⁿ}, {ww}, context-sensitive languages
- Key insight: Stack enables unbounded counting and matching
- Traces: Show complete configuration sequence
- Applications: Parsing, compiler design, nested structures
Detailed examples demonstrate how to design PDAs for various context-free languages!