CD Notes
Complete guide to Pushdown Automata including formal definition, PDA construction, acceptance by final state and empty stack, and relationship with context-free grammars and parsers.
Introduction
A Pushdown Automaton (PDA) extends a finite automaton with an auxiliary stack memory, giving it the power to recognize context-free languages. This additional memory is what allows compilers to parse nested structures like balanced parentheses, nested if-else blocks, and recursive function calls that finite automata cannot handle.
PDAs are the theoretical model behind every parser — whether it is a recursive descent parser (which uses the program call stack) or a table-driven LR parser (which maintains an explicit stack).
Formal Definition
A PDA is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:
- Q = finite set of states
- Σ = input alphabet
- Γ = stack alphabet
- δ = transition function, δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
- q₀ = start state
- Z₀ = initial stack symbol (bottom marker)
- F = set of final states
A transition δ(q, a, X) = {(p, γ)} means: in state q, reading input a, with X on top of stack, move to state p and replace X with string γ on the stack.
PDA Operations
Stack operations encoded in transitions
- PUSH: δ(q, a, X) = {(p, YX)} → push Y, X remains
- POP: δ(q, a, X) = {(p, ε)} → pop X
- REPLACE: δ(q, a, X) = {(p, Y)} → replace X with Y
- NO-OP: δ(q, a, X) = {(p, X)} → leave stack unchanged
Example notation
(q0, a, Z₀) → (q1, AZ₀) means: push A
(q1, b, A) → (q1, ε) means: pop A
(q1, ε, Z₀) → (q2, Z₀) means: transition on empty input
Acceptance Modes
Acceptance by Final State
The PDA accepts w if after reading all of w, it can reach a state in F (regardless of stack contents).
Acceptance by Empty Stack
The PDA accepts w if after reading all of w, the stack is empty (regardless of current state).
Both modes are equivalent in power — any language accepted by one mode can be accepted by the other.
PDA Construction Examples
Example 1: PDA for L = {aⁿbⁿ | n ≥ 1}
PDA (acceptance by empty stack)
States: {q0, q1}
Σ = {a, b}, Γ = {A, Z₀}
Start: q0, Initial stack: Z₀
Transitions
δ(q0, a, Z₀) = {(q0, AZ₀)} // first a: push A
δ(q0, a, A) = {(q0, AA)} // more a's: push A
δ(q0, b, A) = {(q1, ε)} // first b: pop A, switch state
δ(q1, b, A) = {(q1, ε)} // more b's: pop A
δ(q1, ε, Z₀) = {(q1, ε)} // all matched: empty stack
Trace for "aaabbb"
(q0, aaabbb, Z₀)
⊢ (q0, aabbb, AZ₀) push A
⊢ (q0, abbb, AAZ₀) push A
⊢ (q0, bbb, AAAZ₀) push A
⊢ (q1, bb, AAZ₀) pop A
⊢ (q1, b, AZ₀) pop A
⊢ (q1, ε, Z₀) pop A
⊢ (q1, ε, ε) empty stack → ACCEPT
Example 2: PDA for L = {ww^R | w ∈ {a,b}*}
| States | {q0, q1, q2} |
| Start | q0, Final: {q2} |
| // Phase 1 | Push first half (guessing midpoint) |
| // Non-deterministic switch to Phase 2 (guess | midpoint reached) |
| // Phase 2 | Match and pop second half |
| δ(q1, ε, Z₀) = {(q2, Z₀)} // stack empty except Z₀ | accept |
| ⊢ (q1, ba, BAZ₀) // ε-transition | guess midpoint |
Example 3: PDA for Balanced Parentheses
| States | {q0, q1}, Start: q0, Final: {q1} |
| δ(q0, ε, Z₀) = {(q1, Z₀)} // balanced | accept |
| ⊢ (q1, ε, Z₀) | ACCEPT |
Deterministic PDA (DPDA)
A DPDA has at most one move in any configuration:
- For each (q, a, X): |δ(q, a, X)| + |δ(q, ε, X)| ≤ 1
CFG to PDA Conversion
For any CFG G, we can construct an equivalent PDA:
Algorithm (Top-down construction)
Given G = (V, T, P, S):
1. PDA has states {q0, q1, q2}
2. Start: push S, go to q1
δ(q0, ε, Z₀) = {(q1, SZ₀)}
3. For each production A → α:
δ(q1, ε, A) = {(q1, α)} // expand non-terminal
4. For each terminal a:
δ(q1, a, a) = {(q1, ε)} // match terminal
5. Accept: δ(q1, ε, Z₀) = {(q2, ε)}
Example: Grammar S → aSb | ε
PDA transitions
δ(q0, ε, Z₀) = {(q1, SZ₀)}
δ(q1, ε, S) = {(q1, aSb), (q1, ε)} // two productions
δ(q1, a, a) = {(q1, ε)}
δ(q1, b, b) = {(q1, ε)}
δ(q1, ε, Z₀) = {(q2, ε)}
PDA to CFG Conversion
| 1. Variables | [qXp] for all q,p ∈ Q, X ∈ Γ |
| 2. Start symbol: S with S | [q₀Z₀q] for all q ∈ Q |
| Add: [qXsₖ] | a[rY₁s₁][s₁Y₂s₂]...[sₖ₋₁Yₖsₖ] |
| Add: [qXr] | a |
PDA and Parser Connection
Two-Stack PDA and Turing Machines
A PDA with two stacks is equivalent to a Turing Machine:
Interview Questions
- Q: Why can't a DFA recognize {aⁿbⁿ}? What does the PDA use that the DFA lacks?
A: A DFA has fixed finite memory (states) and cannot count arbitrarily large n. The PDA uses its stack as unbounded memory — it pushes one symbol per 'a' and pops one per 'b'. When the stack empties after all b's, counts are equal.
- Q: Is the language {aⁿbⁿcⁿ} recognizable by a PDA?
A: No. A PDA has only one stack. It can match a's with b's (push a's, pop for b's), but then has no memory left to verify the c-count matches. This language is context-sensitive, requiring a linear bounded automaton.
- Q: What is the connection between DPDA and LR parsers?
A: Every LR(1) parser is essentially a DPDA. The parser stack stores states and grammar symbols. Shift moves push onto the stack (reading input), and reduce moves pop the RHS and push the LHS (like PDA stack operations). The parsing table makes it deterministic.
- Q: Can every CFL be recognized by a DPDA?
A: No. Inherently ambiguous CFLs and some unambiguous CFLs (like {ww^R | w ∈ {a,b}*}) require non-determinism. However, all practical programming languages are DCFLs and can be parsed by DPDAs.
- Q: How does acceptance by empty stack differ from acceptance by final state in practice?
A: Final state acceptance is more natural for parsers (accept when reduce to start symbol succeeds). Empty stack acceptance is cleaner theoretically. In practice, LR parsers use a combination — they accept when the stack contains only the start symbol and input is exhausted, essentially a final-state approach.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Pushdown Automata (PDA) in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, automata, and, formal, languages
Related Compiler Design Topics