Push-Down Automata

Push-Down Automata

1. What It Is

A push-down automaton (PDA) is a finite automaton plus a stack — the machine model for context-free languages. The parser is essentially a PDA: shift tokens, push/pop on stack, accept on empty stack or final state.

7-tuple: states Q, input $Σ$, stack alphabet $Γ$, transition $δ$, start $q₀$, start stack $Z₀$, finals F.

2. How It Works

input → [finite control + stack top] → push / pop / move

• Push: remember an opening ((, {, call) for later matching.
• Pop: match a closing against stack top.
• If top mismatches → reject.

3. Example — balanced parentheses

states: q0 (working), q1 (accept)
q0, ε, Z0 → push Z0 (init)
q0, (, X → push ( onto X
q0, ), ( → pop
q0, ε, Z0 → go q1 (accept when input over + stack has only Z0)

Trace (()):

stack: [Z0] → [( Z0] → [(( Z0] → [( Z0] → [Z0] → accept

Language { $aⁿbⁿ$ }: push A for each a, pop one A per b; accept iff stack empty at end.

4. PDA vs FA, PDA vs CFG

• FA + stack = PDA; FA alone cannot count.
• Every CFG has an equivalent PDA and vice versa (top-down PDA simulates leftmost derivation, bottom-up simulates rightmost in reverse).
• Deterministic PDA (DPDA) ⊂ nondeterministic PDA — unlike FA. LR parsers use DPDA; general CFLs need NPDA.

5. Exam Points

• Define PDA + stack role with diagram — 5 marks, very frequent.
• Trace PDA for aⁿbⁿ / balanced parens — 5 marks, frequent.
• PDA ≡ CFG, DPDA vs NPDA — 3 marks, frequent.