THE PUSHDOWN AUTOMATON a finite machine plus one stack; exactly the context-free
A finite automaton cannot count — it has no memory beyond its current state, so it cannot check that every open bracket has a close. Give it one stack and it can: push on open, pop on close, accept if the stack ends empty. That single stack is the exact jump from regular to context-free languages — the class that grammars, arithmetic, and nested structure live in.
THE TECHNIQUE push on open, pop on close, end empty
The classic non-regular language: balanced brackets. A DFA fails (it cannot remember the depth); a pushdown automaton succeeds with a stack. Watch the stack depth rise and fall — accept only if it ends at 0 and never goes negative: live demo
HISTORY & CREDIT Oettinger 1961; Chomsky-Schutzenberger
“One stack, two stacks, it is all the same power.” — no. A pushdown automaton with one stack recognises the context-free languages; give it a second stack and it becomes a full Turing machine (the two stacks simulate a tape). Each unit of memory is a discrete jump up the hierarchy. cited
1961 · Anthony Oettinger — “Automatic syntactic analysis and the pushdown store”: the pushdown automaton formalised. 1962 · Chomsky and Schützenberger, and Evey — prove PDAs recognise exactly the context-free languages (Chomsky’s 1956 hierarchy gets its machine). context · the LR/LL parsers of the compiler front-end (batches 22–23) are deterministic PDAs — a stack automaton driving the parse.
The parser you already met (batch 22) is a pushdown automaton wearing a table: its parse stack is the store, and a shift is a push, a reduce a pop. Nested structure needs a stack; a stack is what a PDA has. Oettinger 1961
RECOMMEND FOR I-13 accept by empty stack, computed
The bracket PDA runs on the canonical compiler as a stack-depth counter — accept iff it ends at 0 and never underflows:
$ i13 run pda.i13 # +1 on '(', -1 on ')'; reject on underflow
(()()) -> depth 0 ACCEPT (balanced)
(() -> depth 1 reject (one bracket unclosed)
)( -> depth -1 reject (closed before opened)
Recommend: the pushdown automaton is LIT and already inside I-13 — verified the bracket PDA accepts (()()) (depth returns to 0), rejects (() (ends at 1) and )( (underflows to −1), all as a native recursion carrying one integer of stack depth. I-13’s own parser (batch 22) is a deterministic PDA; a general one needs a real stack of symbols (an array + top index), which the bounded array already provides. It is the machine one notch above the DFA and one notch below the Turing machine (175’s two-stack remark) — the exact home of nested structure.