a pushdown automaton
/ PUSH-down aw-TOM-uh-ton /
A finite automaton is like a turnstile that only remembers which state it is in — and that is its fatal weakness: with a fixed number of states it cannot count without bound, so it cannot tell whether a string has as many a's as b's. The fix is small but powerful: give the machine one extra resource, a stack — a pile of notes where you can only ever look at, add to, or remove the TOP slip. A pushdown automaton is exactly a finite-state control plus a single stack, and that one addition lifts it from regular languages all the way up to the context-free languages.
The picture in action: to recognise the language a^n b^n (the same number of a's followed by the same number of b's), the PDA reads the input left to right. For each a it sees, it pushes one marker onto the stack; once the b's begin, for each b it pops one marker off. If the stack runs out exactly when the input ends, the counts matched and the machine accepts; otherwise it rejects. The stack is its unbounded but access-restricted memory: unlimited depth, but you only ever touch the top. This is precisely the counting that a finite automaton, with its finite memory, can never do.
Pushdown automata matter because they are the MACHINE counterpart of context-free grammars: the two describe exactly the same class of languages, the context-free languages, just as finite automata and regular expressions describe the regular languages. They are the theory behind parsers, the data structure behind recursion, and the reason a stack of pending function calls or unclosed brackets is the natural model for nested structure. One honest caveat up front: in general a PDA is nondeterministic, and unlike finite automata its deterministic version is strictly weaker — a difference that turns out to matter enormously for real compilers.
On input aabb, the PDA pushes X, X (two a's), then on each b pops an X; after the second b the stack holds only the initial symbol Z0 and the input is finished, so it accepts. On aab it would still have an X left over and reject.
A finite control plus one stack: push to remember, pop to match, and the stack provides unbounded counting.
A PDA has exactly ONE stack with last-in-first-out access; it is not a Turing machine's freely read-write tape. That single restriction is why PDAs capture context-free languages and no more.