Pushdown Automata (PDA)
A pushdown automaton is a finite automaton augmented with a stack — an infinite LIFO (last-in, first-out) data structure. The stack gives the machine the ability to "remember" an unbounded amount of information, which finite automata cannot do. This extra power allows PDAs to recognize exactly the context-free languages.
Formal Definition
A PDA is a 7-tuple M = (Q, Σ, Γ, δ, q0, Z0, F), where:
Q — finite set of states
Σ — input alphabet
Γ — stack alphabet (includes Σ)
δ — transition function
Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
q0 — start state
Z0 — initial stack symbol
F — set of accept states
A transition δ(q, a, X) = {(p, γ)} means:
In state q, reading input a, with X on top of stack:
Move to state p, replace X with γ on the stack.Example: PDA for {a^n b^n | n >= 1}
The stack counts how many a's we've seen. For each b, we pop one a. If the stack is empty (except for the initial symbol) after reading all input, the string is accepted.
PDA for {a^n b^n | n >= 1}:
Transitions:
δ(q0, a, Z0) = {(q0, AZ0)} — push A for each a
δ(q0, a, A) = {(q0, AA)} — push A for each a
δ(q0, b, A) = {(q1, ε)} — pop A for each b
δ(q1, b, A) = {(q1, ε)} — pop A for each b
δ(q1, ε, Z0) = {(q1, Z0)} — accept if stack is
back to Z0
Trace "aabb":
Start: state q0, input "aabb", stack [Z0]
Read a: push A → stack [A, Z0]
Read a: push A → stack [A, A, Z0]
Read b: pop A → stack [A, Z0]
Read b: pop A → stack [Z0]
ε-transition to accept state q1 ✓Acceptance by Final State vs Empty Stack
There are two ways a PDA can accept:
1. By final state:
The PDA ends in an accept state after consuming
all input. This is the standard definition.
2. By empty stack:
The PDA empties its stack after consuming all input.
No accept states needed.
These two methods are equivalent — any PDA using one
method can be converted to use the other.PDAs vs DFAs vs TMs
A PDA is strictly more powerful than a DFA. The language {a^n b^n | n >= 0} is context-free but not regular — no DFA can recognize it, but a PDA can. However, a PDA is strictly less powerful than a Turing machine. There are context-sensitive and recursively enumerable languages that no PDA can handle.
The stack is the key difference. A DFA has no memory (beyond its current state). A PDA has a stack that can grow infinitely. A Turing machine has an infinite tape that can be read and written in both directions.