Pushdown Automata (PDA)

A PDA is a finite automaton plus a stack. It's a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F), where Γ is the stack alphabet, Z₀ the initial stack symbol and δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ*.

PDA for L = {aⁿbⁿ | n ≥ 1}

δ(q0, a, Z0) = (q0, aZ0)     push a
δ(q0, a, a)  = (q0, aa)      push a
δ(q0, b, a)  = (q1, ε)       first b: pop a
δ(q1, b, a)  = (q1, ε)       pop a for each b
δ(q1, ε, Z0) = (qf, Z0)      accept by final state

Instantaneous Descriptions for aabb

(q0, aabb, Z0) ⊢ (q0, abb, aZ0) ⊢ (q0, bb, aaZ0) ⊢ (q1, b, aZ0) ⊢ (q1, ε, Z0) ⊢ (qf, ε, Z0)
Accepted.

Acceptance

A PDA can accept by final state or by empty stack. The two are equivalent in power.

DPDA vs NPDA