The idea: a finite automaton plus one stack
A DFA reads its input once, left to right, and all it remembers is which of its finitely many states it is in. A pushdown automaton (PDA) is the same machine with one extra thing: a stack it can push symbols onto and pop them off, with no size limit. It can only see the top of the stack. That one addition is enough to count, and counting is exactly what the language aⁿbⁿ (some a's, then the same number of b's) needs.
Pick an input and press Run. Orange marks the current state and symbol, red marks the rule being used, blue marks an A on its way onto the stack. The DFA at the bottom reads the same input at the same time.
One move: read, look at the top, replace the top
Each rule of a PDA says: in state q, reading symbol x (or nothing, ε), with Y on top of the stack, go to state p and replace Y by the string γ. It is written x, Y / γ on the edge from q to p. Replacing Y by AY pushes an A; replacing Y by ε pops Y; replacing Y by Y leaves the stack alone. The stack starts with only the bottom marker Z, so the machine can tell when it is empty.
| rule | state | read, top / replace | go to | effect |
|---|---|---|---|---|
| 1 | q0 | a, Z / AZ | q0 | first a: push A |
| 2 | q0 | a, A / AA | q0 | another a: push A |
| 3 | q0 | b, A / ε | q1 | first b: pop A |
| 4 | q1 | b, A / ε | q1 | next b: pop A |
| 5 | q1 | ε, Z / Z | q2 | all a's matched: accept state |
The PDA accepts if it has read the whole input and is in the accept state q2. If no rule fits, it halts and rejects. At most one rule fits at any time, so this PDA is deterministic.
Counting with the stack
While it reads a's, the PDA stays in q0 and pushes one A per a, so the number of A's on the stack is the number of a's read so far. The first b moves it to q1, and each b pops one A. When only Z is left, every a has been matched by a b, and rule 5 moves to q2 without reading anything (Demo: aabb is accepted).
The states q0 and q1 also enforce the order: once the PDA is in q1 there is no rule for a, so an a after a b ends the run.
Why no DFA can do it
To accept aⁿbⁿ, a machine must still know n after reading the a's. A DFA with k states, after reading a, aa, …, aᵏ⁺¹, has seen k + 1 different prefixes but has only k states, so by the pigeonhole principle two of them, aⁱ and aʲ with i ≠ j, end in the same state. From there it acts the same on bⁱ, so it accepts aⁱbⁱ and aʲbⁱ alike, or rejects both. Either way it is wrong. This is the argument behind the pumping lemma for regular languages.
The DFA on the canvas makes the limit concrete. Its states A0 to A3 count the a's, B2 to B0 count the b's still owed, and B0 accepts. It is correct for n ≤ 3, but on the fourth a it has no state left (Demo: aaaabbbb, the DFA runs out of states). Adding states only moves the limit; the PDA's stack has none.
How a run is rejected
| input | what happens | why |
|---|---|---|
| aaabb | input ends in q1 with AZ on the stack | more a's than b's (Demo: aaabb) |
| aabbb | after aabb it is in q2; no rule for the last b | more b's than a's (Demo: aabbb) |
| abab | no rule for a in q2 | an a after a b (Demo: abab) |
| ba | no rule for b with Z on top in q0 | a b with no a to match it |
PDAs and context-free languages
The same language has a two-rule grammar: S → a S b | a b. Each use of the first rule wraps one more a…b pair around the middle, just as each A on the stack waits for its b. In general, PDAs (nondeterministic ones) recognize exactly the context-free languages, the languages of context-free grammars. They sit one level above the regular languages of DFAs and regexes, and one below what a Turing machine can decide.
Balanced parentheses, nested if/else blocks and arithmetic with brackets are all context-free, which is why every parser keeps a stack. Regex to NFA to DFA shows the regular level, CYK Parsing decides membership in a context-free language with a table instead of a stack, and Inside a Tiny Compiler parses with recursive descent, where the call stack plays the PDA's stack. A DFA is the same machine as the hardware in Finite State Machines; the stack itself is the one in Stack (array).
Give the machine a tape it can read and write in both directions and it can compute anything computable: see Turing Machine.
What the page leaves out
Nondeterministic PDAs (needed for even-length palindromes wwᴿ: the machine must guess the middle, and no deterministic PDA can), acceptance by empty stack, the constructions between grammars and PDAs, the pumping lemma for context-free languages (it shows that aⁿbⁿcⁿ is not context-free), closure properties, and n = 0 (the empty string is left out of this language to keep the machine deterministic and small).
See where this page fits on the Logic, Sets & Counting mind map.