Pushdown Automata

Math for CS · Axiom Academy

Finite automata + a stack = the power to recognize context-free languages A DFA cannot count, so it cannot recognize . What is the smallest fix? A DFA's only memory is its current state — a finite snapshot. To accept a^nb^n for arbitrary n , the machine would need to remember n exactly, which requires unboundedly many states. So we will add memory in the cheapest possible way: a single stack. A stack is the simplest unbounded memory structure: you only see the top, you can only push or pop. This restriction is exactly enough to count nested structure (push on the way down, pop on the way back up) without giving the machine the full power of a Turing machine. A PDA is a 6-tuple. The new pieces compared to a DFA are the stack alphabet and the stack-aware transition function. is the stack alphabet (often includes a special bottom-of-stack marker ) A single transition means: in state q , reading input symbol a , with X on top of the stack, move to state p , pop X , and push the string onto the stack. Either a or X may be , meaning "no input read" or "no pop." The codomain is — a set of possible next configurations. This makes the standard model nondeterministic . We will see why nondeterminism matters in Step 5. The classic warm-up. Push an X for every a , then pop one for every b . Take , , \ . The transitions are: read b , pop X , switch to q_1 read more b 's, pop X each time ) (q_ , ) stack is empty, accept

This is the written version of the interactive lesson above. See the full Math for CS course.