The language aⁿbⁿ (some a's followed by the same number of b's) is the standard first example of a language no finite automaton can recognise: a DFA has no way to count arbitrarily high. A pushdown automaton (PDA) is a finite automaton with a stack, and the stack is exactly the counter it needs.
The idea
Read the a's and push one symbol for each. When the b's start, pop one symbol per b. If the stack is back to its bottom marker exactly when the input runs out, the counts matched.
The transitions
States q0 (reading a's), q1 (reading b's) and q2 (accept). The stack starts with Z, a marker for "empty". Each rule reads state, input, top of stack → new state, what to push (top first; ε means push nothing, i.e. just pop).
q0, a, Z → q0, AZ first a: push A on top of Z
q0, a, A → q0, AA more a's: push another A
q0, b, A → q1, ε first b: pop an A, switch to reading b's
q1, b, A → q1, ε more b's: pop an A each
q1, ε, Z → q2, Z back to Z with no input left: accept
q0, ε, Z → q2, Z empty input (n = 0) is also accepted
Accept by final state q2.
Trace on aabb (accepted)
| Step | State | Input left | Stack (top first) | Rule used |
|---|---|---|---|---|
| 0 | q0 | aabb | Z | start |
| 1 | q0 | abb | AZ | q0, a, Z → q0, AZ |
| 2 | q0 | bb | AAZ | q0, a, A → q0, AA |
| 3 | q1 | b | AZ | q0, b, A → q1, ε |
| 4 | q1 | ε | Z | q1, b, A → q1, ε |
| 5 | q2 | ε | Z | q1, ε, Z → q2, Z |
Traces that reject
- aab: after two a's the stack is AAZ; one b pops it to AZ, and then the input is empty with an A still on the stack. No rule moves from q1 with an A on top and no input, so the PDA is stuck in a non-accepting state. Too many a's.
- abb: one a pushes A; the first b pops it back to Z; the second b finds Z on top, and there is no rule for (q1, b, Z). Stuck. Too many b's.
- ba: no rule reads b in q0 with Z on top, so it fails immediately. Order matters.
Final state or empty stack?
Textbooks use two acceptance conditions, and both define the same class of languages (the context-free languages):
- Final state: accept if the PDA is in an accepting state when the input runs out (used above).
- Empty stack: accept if the stack is completely empty when the input runs out. For this machine you would pop Z too, e.g.
q1, ε, Z → q1, ε, and drop q2.
Exam questions usually say which one to use; if they don't, state your choice.
Determinism
This PDA is deterministic: in every configuration at most one rule applies. Many context-free languages need nondeterminism, such as even-length palindromes wwᴿ, where the PDA has to guess where the middle is. Unlike finite automata, nondeterministic PDAs are strictly more powerful than deterministic ones.
Common mistakes
- Forgetting the bottom marker. Without Z, the machine can't tell "stack empty" from "stack has something".
- Allowing a's after b's. Once in q1 there must be no rule that reads a, or the PDA would accept strings like abab.
- Mixing up the push order. "Push AZ" means A ends up on top of Z.
- Leaving out n = 0. If the language is aⁿbⁿ with n ≥ 0, the empty string must be accepted (the last rule).
Try it
The PDA simulator has this machine as a built-in example. Type any input and step through it with the stack shown at every move; nondeterministic PDAs, ε-moves and both acceptance modes are supported. When you get to Turing machines, the Turing machine simulator solves aⁿbⁿ without a stack, by marking symbols on the tape.
For a related walkthrough, read NFA vs DFA: The Difference Explained.