The one thing a DFA could never do
By now you have two ways to describe the same world. From the regular-language rungs you trust a DFA: a turnstile-like machine that remembers only its current state. From the grammar rung you trust a context-free grammar: a finite list of rules whose recursion (S → a S b, S → ( S )) generates unbounded, matched nesting. The nagging question this rung answers is: is there a machine — a step-by-step reader, not a generator — whose raw power matches a grammar's? A DFA is hopeless here, because to recognise a^n b^n it would have to remember how many a's it has seen, and its fixed, finite set of states simply cannot hold an unbounded count.
So the fix is not a cleverer set of states — no finite control will ever count without bound. The fix is to hand the machine one extra piece of memory. But which? A freely read-write notebook would be too much (that overshoots all the way to a Turing machine, which is far stronger than any grammar). The surprise of this rung is that a single, severely restricted memory is exactly the right amount. That memory is a stack.
A stack of plates as memory
Picture a spring-loaded pile of cafeteria plates. You can only ever put a plate ON TOP (push) or take the TOP plate off (pop) — you cannot reach into the middle or peek at the bottom. That is the whole vocabulary of a stack as memory, and it is the single extra resource a pushdown automaton gets beyond its finite control. Two properties make it the perfect amount of power. First, it is unbounded: the pile can grow as tall as needed, so the machine can remember an arbitrarily large count — one plate per a, with no fixed limit. Second, its access is restricted: at any instant only the top is visible; everything underneath is locked away until the plates above are popped off.
Here is the picture in action on a^n b^n (equal a's then equal b's). Read left to right. For each a, push one marker onto the stack. Once the b's begin, for each b pop one marker off. If the stack runs out of markers exactly when the input runs out, the counts matched — accept; if a marker is left over, or the markers run out early, reject. The stack did the one job a DFA could not: it held a count of unbounded size, then spent it back down in lockstep. (You will trace this run move by move in guide 4 of this rung; here just feel why it works.)
Writing the machine down: the seven-tuple
Once the intuition is solid — a finite control plus a stack — we write the whole machine precisely, the way you once pinned down a DFA as a five-part tuple. A pushdown automaton (PDA) is a seven-tuple (Q, Σ, Γ, δ, q0, Z0, F). The pleasing part: compared with a DFA's five parts, a PDA adds exactly two new ingredients, and both describe the stack. New power, two new pieces, nothing more.
Read the seven parts: Q is the finite set of states (the control); Σ (Sigma, the input alphabet) is the set of letters the machine reads; Γ (Gamma, the stack alphabet) is the separate finite set of symbols it may push and pop; δ (delta) is the transition rulebook; q0 is the start state; Z0 is the initial stack symbol sitting on the stack at the start; and F (a subset of Q) is the set of accepting states. The two genuinely new pieces beyond a DFA are Γ and Z0 — the stack's own alphabet and its starting marker.
How the stack actually moves
A DFA transition reads one thing and changes state. A PDA transition reads three things at once and does more. The standard form is δ(q, a, X) = a set of pairs (p, γ): when in state q, reading input symbol a, with X on top of the stack, the machine may move to state p and replace the popped X with the string γ (gamma) of stack symbols. Every PDA move is therefore "pop the top, then push a string," and that one unified rule covers all three cases:
- Pop X and push a LONGER string (e.g. push X X) — a net push, the stack grows by one. This is how each a stacks up another counter marker.
- Pop X and push the empty string ε (epsilon, meaning push nothing) — a pure pop, the stack shrinks by one. This is how each b cancels one marker.
- Pop X and push X back (the same single symbol) — height unchanged, but the machine can still change state. A peek-and-stay.
Two details are easy to miss. First, the input symbol a may be ε — an epsilon-move lets the machine act without consuming any input, purely on the strength of its state and stack top (handy for clean-up steps and for switching modes). Second, the matched-counting trick reveals why a PDA needs a third component in its snapshot. A finite automaton's whole situation is (state, remaining input); a PDA needs (state, remaining input, stack contents) — and that snapshot is called an instantaneous description, or ID. Because the stack can be unboundedly tall, a PDA has infinitely many possible IDs, which is precisely why it can count where a DFA, with finitely many configurations, cannot.
A PDA for a^n b^n (input alphabet Sigma = {a, b}; stack alphabet Gamma = {X, Z0})
delta(q0, a, Z0) = { (q0, X Z0) } in q0, read a, top Z0: push first X above Z0
delta(q0, a, X) = { (q0, X X) } in q0, read a, top X: push another X (grow)
delta(q0, b, X) = { (q1, epsilon) } first b: pop an X, switch to q1
delta(q1, b, X) = { (q1, epsilon) } in q1, read b, top X: pop an X (shrink)
delta(q1, eps, Z0) = { (qf, Z0) } no input left, top Z0: jump to accept state qf
Run on aabb, ID = (state, remaining input, stack top..bottom):
(q0, aabb, Z0) |- (q0, abb, X Z0) push X (read a)
|- (q0, bb, X X Z0) push X (read a)
|- (q1, b, X Z0) pop X (read b, switch to q1)
|- (q1, eps, Z0) pop X (read b)
|- (qf, eps, Z0) accept (epsilon-move, stack back to Z0)Two surprises: matching grammars, and the cost of determinism
Now the headline payoff. The PDA is the machine counterpart of a grammar, in the sharpest possible sense: a language is generated by some context-free grammar if and only if it is recognised by some pushdown automaton. This is the CFG–PDA equivalence, the pushdown echo of "regular expressions equal finite automata" from the rungs below. Both directions are proved by explicit construction — turn any grammar into a PDA that simulates a derivation on its stack, and turn any PDA back into a grammar — so PDAs recognise exactly the context-free languages, no fewer and no more. (Guide 3 of this rung builds both translations.)
But there is a second, deeper surprise hiding in that word "some." A general PDA is nondeterministic: at a given moment it may have several legal moves, and it accepts if SOME sequence of choices leads to acceptance — think of it cloning itself to try every branch, or a lucky guesser who always picks a winning path when one exists. (As with an NFA, this is a precise mathematical device, not randomness and not a real parallel machine.) For some languages the guess is unavoidable: to recognise even-length palindromes like abba, a PDA must push the first half and guess where the middle is before it starts matching — and there is no way to compute that midpoint in advance.
Here is where pushdown automata break from finite automata in a way that genuinely surprises everyone. For finite automata, nondeterminism is free: every NFA has an equivalent DFA, so guessing only buys conciseness. For pushdown automata, this is false. A deterministic PDA (one legal move at every step) recognises strictly fewer languages than a nondeterministic one — even-length palindromes are context-free yet no deterministic PDA recognises them, while a^n b^n IS deterministic (the input itself signals when to switch from pushing to popping). The languages a DPDA can handle are called the deterministic context-free languages, a proper subset of all context-free languages. This asymmetry is not a footnote: it is exactly why real compilers restrict their grammars to the deterministic kind (LL, LR), so a parser can run forward in linear time with no backtracking. Guide 5 of this rung is devoted to it.