Pushdown Automata

What is a Pushdown Automaton?

Pushdown Automaton (PDA) is a finite automaton with an additional stack memory.

Simple Analogy

Think of PDA like a person reading with sticky notes:

Finite automaton: Person reading (can see current character)
Stack: Stack of sticky notes (can add/remove from top)
Reading: Process input character by character
Memory: Stack remembers previous information

Example: Matching parentheses

See ’(’ → Put sticky note on stack
See ’)’ → Remove sticky note from stack
All matched if stack empty at end!

Why PDA?

Finite automata are limited:

Can’t count unboundedly
Can’t match {aⁿbⁿ}
Can’t handle nested structures

PDA adds stack:

Can count using stack
Can match {aⁿbⁿ} ✓
Can handle nested structures ✓
Exactly recognizes context-free languages!

Key Concept: The Stack

Stack (Last-In-First-Out):

Operations:
- Push: Add symbol to top
- Pop: Remove symbol from top
- Look: See top symbol (without removing)

Example:
Start: [empty]
Push A: [A]
Push B: [B, A]
Push C: [C, B, A]
Pop: [B, A]  (C removed)
Pop: [A]     (B removed)

Top of stack is the only accessible position!

Formal Definition

Pushdown Automaton is a 7-tuple:

PDA = (Q, Σ, Γ, δ, q₀, Z₀, F)

Where:

Q: Finite set of states
Σ: Input alphabet (input symbols)
Γ: Stack alphabet (stack symbols)
δ: Transition function
q₀: Start state (q₀ ∈ Q)
Z₀: Initial stack symbol (Z₀ ∈ Γ)
F: Set of accepting/final states (F ⊆ Q)

Transition Function δ

Most important component!

Form:

δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)

Meaning:

δ(current_state, input_symbol, top_of_stack)
  = {(next_state, symbols_to_push), ...}

Example:

δ(q₀, a, Z₀) = {(q₁, AZ₀)}

Interpretation:

In state q₀
Reading input ‘a’
Stack top is Z₀
Go to state q₁
Pop Z₀, push A then Z₀ (net: push A)

Note: Can have multiple possible transitions (non-deterministic!)

How PDA Works

Configuration

PDA configuration = (state, remaining_input, stack_contents)

Example: (q₀, aabb, Z₀)

State: q₀
Remaining input: “aabb”
Stack: [Z₀] (bottom to top)

Transition (Move)

When: (q, aw, Xα) where

q = current state
a = next input symbol (or ε)
w = remaining input
X = top of stack
α = rest of stack

If: δ(q, a, X) contains (p, β)

Then: Move to (p, w, βα)

New state: p
Consumed ‘a’ from input (or nothing if ε-transition)
Popped X, pushed β
Stack becomes: [β, α] (β on top)

Accepting Input

Two ways to accept (we’ll see both later):

By final state: Input consumed, reach state in F
By empty stack: Input consumed, stack empty

Both are equivalent in power!

Example 1: Simple PDA for {aⁿbⁿ}

Language: {ab, aabb, aaabbb, …}

Design Idea

1. Push symbol for each 'a'
2. Pop symbol for each 'b'
3. Accept if stack empty

Formal PDA

Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {A, Z₀}
q₀ = q₀ (start state)
Z₀ = Z₀ (initial stack symbol)
F = {q₂} (final state)

Transitions:

δ(q₀, a, Z₀) = {(q₀, AZ₀)}    // First 'a': push A
δ(q₀, a, A) = {(q₀, AA)}       // More 'a's: push A
δ(q₀, b, A) = {(q₁, ε)}        // First 'b': pop A, go to q₁
δ(q₁, b, A) = {(q₁, ε)}        // More 'b's: pop A
δ(q₁, ε, Z₀) = {(q₂, Z₀)}      // Done: go to final state

Trace for “aabb”

Configuration: (state, input, stack)

(q₀, aabb, Z₀)      // Start
├─ Read 'a', δ(q₀, a, Z₀) = (q₀, AZ₀)
(q₀, abb, AZ₀)      // Pushed A
├─ Read 'a', δ(q₀, a, A) = (q₀, AA)
(q₀, bb, AAZ₀)      // Pushed another A
├─ Read 'b', δ(q₀, b, A) = (q₁, ε)
(q₁, b, AZ₀)        // Popped A, moved to q₁
├─ Read 'b', δ(q₁, b, A) = (q₁, ε)
(q₁, ε, Z₀)         // Popped A
├─ ε-transition, δ(q₁, ε, Z₀) = (q₂, Z₀)
(q₂, ε, Z₀)         // Final state, ACCEPT! ✓

Accepted! ✓

Trace for “aaab” (rejected)

(q₀, aaab, Z₀)
(q₀, aab, AZ₀)      // Push A
(q₀, ab, AAZ₀)      // Push A
(q₀, b, AAAZ₀)      // Push A
(q₁, ε, AAZ₀)       // Pop A (one 'b' consumed)
// No more input, but stack not empty!
// Can't reach final state
// REJECT! ✗

Rejected! ✗ (stack not empty, can’t reach final state)

Example 2: Balanced Parentheses

Language: {ε, (), (()), ()(), (()()), …}

Design Idea

1. Push symbol for each '('
2. Pop symbol for each ')'
3. Accept if stack empty

Formal PDA

Q = {q₀, qf}
Σ = {(, )}
Γ = {X, Z₀}
Start: q₀
Initial stack: Z₀
Final: {qf}

Transitions:

δ(q₀, (, Z₀) = {(q₀, XZ₀)}    // First '(': push X
δ(q₀, (, X) = {(q₀, XX)}       // More '(': push X
δ(q₀, ), X) = {(q₀, ε)}        // ')': pop X
δ(q₀, ε, Z₀) = {(qf, Z₀)}      // Empty input, accept

Trace 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₀)         // ε-transition, ACCEPT! ✓

Accepted! ✓

Example 3: Palindromes {wwᴿ}

Language: {aa, bb, abba, baab, aabbaa, …}

w = first half, wᴿ = reverse of w

Design Idea (Non-deterministic!)

1. Push symbols onto stack
2. Guess middle of string (ε-transition)
3. Match remaining input with stack (pop and compare)
4. Accept if stack empty

Why Non-deterministic?

Can’t know where middle is!

Example: “abba”

Middle could be after “a” → try matching “bba” with stack
Middle could be after “ab” → try matching “ba” with stack ✓

PDA guesses and explores all possibilities!

Formal PDA

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

Transitions:

// Phase 1: Push onto stack
δ(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: Guess middle (non-deterministic!)
δ(q₀, ε, Z₀) = {(q₁, Z₀)}
δ(q₀, ε, A) = {(q₁, A)}
δ(q₀, ε, B) = {(q₁, B)}

// Phase 3: Match and pop
δ(q₁, a, A) = {(q₁, ε)}    // 'a' matches A on stack
δ(q₁, b, B) = {(q₁, ε)}    // 'b' matches B on stack
δ(q₁, ε, Z₀) = {(q₂, Z₀)}  // Accept

Trace for “abba”

Configuration: (state, input, stack)

(q₀, abba, Z₀)      // Start
(q₀, bba, AZ₀)      // Push A for 'a'
(q₀, ba, BAZ₀)      // Push B for 'b'
(q₀, ba, BAZ₀)      // ε-transition: guess middle!
(q₁, ba, BAZ₀)      // Now in matching phase
(q₁, a, AZ₀)        // Pop B (matched 'b')
(q₁, ε, Z₀)         // Pop A (matched 'a')
(q₂, ε, Z₀)         // ACCEPT! ✓

Accepted! ✓

Deterministic vs Non-deterministic PDA

Non-deterministic PDA (NPDA)

Can have:

Multiple transitions for same (state, input, stack)
ε-transitions
Guessing/branching

Example: Palindromes (guessing middle)

Deterministic PDA (DPDA)

Must have:

At most one transition for each (state, input, stack)
No ε-transition conflicts
No guessing

Example: {aⁿbⁿ} (deterministic counting)

Important Fact

NPDA is more powerful than DPDA!

Example:

NPDA can recognize all CFLs
DPDA can only recognize deterministic CFLs (subset)
Palindromes (wwᴿ) requires NPDA

This is different from finite automata (NFA = DFA in power)

PDA Design Strategies

Strategy 1: Counting

Use case: Languages like {aⁿbⁿ}, {aⁿbⁿcⁿ}… wait, third one impossible!

Method:

Push symbol for each occurrence of first character
Pop symbol for each occurrence of second character
Accept if matched

Works for: {aⁿbⁿ}, {aⁿbᵐcⁿ}, but NOT {aⁿbⁿcⁿ} (need 2 counters!)

Strategy 2: Matching

Use case: Balanced parentheses, nested structures

Method:

Push for opening delimiter
Pop for closing delimiter
Accept if balanced

Works for: Parentheses, brackets, XML tags

Strategy 3: Guessing Middle

Use case: Palindromes, symmetric structures

Method:

Push first half
Guess middle (ε-transition)
Match second half

Requires: Non-determinism

Strategy 4: Comparing Substrings

Use case: {wwᴿ}, {w#wᴿ}

Method:

Store first substring on stack
Compare with second substring
Accept if match

Requires: Clear separator or guessing

Limitations of PDA

What PDA Can Do ✓

{aⁿbⁿ}: Count one type
{wwᴿ}: Match symmetric
Balanced parentheses: Nested structures
{aⁿbⁿcᵐ}: Independent counts

What PDA Cannot Do ✗

{aⁿbⁿcⁿ}: Need 2 counters (only have 1 stack!)
{ww}: Need to remember and compare (no central marker)
{aⁿ² }: Quadratic growth (stack linear)
Context-sensitive languages: Too complex

Key limitation: Only one stack (not multiple stacks or queues)

PDA Computation Tree

Non-deterministic PDA creates computation tree:

        (q₀, abba, Z₀)
       /              \
Push A              Don't push (guess)
      |                     |
(q₀, bba, AZ₀)    ...other paths...
     /      \
Push B    Guess middle
   |             |
(q₀,ba,BAZ₀)  ...
   |
Guess middle
   |
(q₁,ba,BAZ₀)
   |
  ...
   |
ACCEPT ✓

Accept if ANY path leads to acceptance

Reject if ALL paths reject

Important Theorems

Theorem 1: Equivalence with CFG

Theorem: PDAs recognize exactly the context-free languages

For every CFG, there exists a PDA that recognizes L(G)

For every PDA, there exists a CFG that generates L(PDA)

This is huge! CFGs and PDAs are equivalent!

Theorem 2: Two Acceptance Modes

Theorem: PDA by final state ≡ PDA by empty stack

Can convert between them while preserving language

Both are equally powerful!

Theorem 3: DPDA ⊂ NPDA

Theorem: Deterministic PDA is strictly weaker than non-deterministic PDA

Example: {wwᴿ} recognized by NPDA but not DPDA

Different from finite automata! (where NFA = DFA)

Important Exam Points

✓ PDA definition: 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F)
✓ Stack: LIFO structure, only top accessible
✓ Transition: δ(state, input, stack_top) = {(next_state, push_symbols)}
✓ Configuration: (state, remaining_input, stack_contents)
✓ Two acceptance modes: By final state or empty stack (equivalent)
✓ Non-determinism: Can guess, explore multiple paths
✓ Equivalence: PDA ≡ CFG (same power)
✓ DPDA vs NPDA: DPDA strictly weaker
✓ Design strategies: Counting, matching, guessing middle
✓ Limitations: Only one stack, can’t recognize {aⁿbⁿcⁿ}

Common Mistakes to Avoid

✗ Mistake 1: Forgetting to pop before push
✓ Correct: δ(q, a, X) = (p, YZ) means pop X, push Z then Y

✗ Mistake 2: Assuming PDA is deterministic
✓ Correct: PDAs are non-deterministic by default

✗ Mistake 3: Accessing bottom of stack
✓ Correct: Only top of stack accessible

✗ Mistake 4: Thinking DPDA = NPDA in power
✓ Correct: NPDA strictly more powerful

✗ Mistake 5: Trying to recognize {aⁿbⁿcⁿ}
✓ Correct: Impossible with one stack

✗ Mistake 6: Confusing push order
✓ Correct: δ(q, a, X) = (p, ABC) pushes C, then B, then A (A on top)

Practice Questions

Q1: What’s the difference between FA and PDA?

Answer: PDA has additional stack memory; FA has only finite states.

Q2: Can PDA recognize {aⁿbⁿcⁿ}?

Answer: No, need two counters but PDA has only one stack.

Q3: What does δ(q₀, a, Z₀) = {(q₁, AZ₀)} mean?

Answer: In state q₀, reading ‘a’, stack top Z₀ → go to q₁, push A (net effect).

Q4: Is every DFA a PDA?

Answer: Yes, PDA without using stack is equivalent to DFA.

Q5: Can DPDA recognize {wwᴿ}?

Answer: No, needs non-determinism to guess middle.

Q6: What’s PDA configuration?

Answer: (state, remaining_input, stack_contents).

Q7: Are PDA and CFG equivalent?

Answer: Yes, they recognize the same class of languages (CFLs).

Q8: How many stacks does PDA have?

Answer: Exactly one stack.

Summary

Pushdown Automaton: FA + stack memory
Components: 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F)
Stack: LIFO, only top accessible
Transition: Based on state, input, and stack top
Non-deterministic: Can guess, explore multiple paths
Two acceptance modes: Final state or empty stack (equivalent)
Power: Recognizes exactly context-free languages
Equivalence: PDA ≡ CFG
DPDA vs NPDA: NPDA strictly more powerful
Design strategies: Counting, matching, guessing
Limitations: One stack, can’t count two independent values
Applications: Parsing, compiler design, nested structures
Key insight: Stack enables unbounded counting and matching

PDA bridges finite automata and context-free grammars, providing a computational model for CFLs!

Pushdown Automata

What is a Pushdown Automaton?

Simple Analogy

Why PDA?

Key Concept: The Stack

Formal Definition

Transition Function δ

How PDA Works

Configuration

Transition (Move)

Accepting Input

Example 1: Simple PDA for {aⁿbⁿ}

Design Idea

Formal PDA

Trace for “aabb”

Trace for “aaab” (rejected)

Example 2: Balanced Parentheses

Design Idea

Formal PDA

Trace for ”(())”

Example 3: Palindromes {wwᴿ}

Design Idea (Non-deterministic!)

Why Non-deterministic?

Formal PDA

Trace for “abba”

Deterministic vs Non-deterministic PDA

Non-deterministic PDA (NPDA)

Deterministic PDA (DPDA)

Important Fact

PDA Design Strategies

Strategy 1: Counting

Strategy 2: Matching

Strategy 3: Guessing Middle

Strategy 4: Comparing Substrings

Limitations of PDA

What PDA Can Do ✓

What PDA Cannot Do ✗

PDA Computation Tree

Important Theorems

Theorem 1: Equivalence with CFG

Theorem 2: Two Acceptance Modes

Theorem 3: DPDA ⊂ NPDA

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App