Q8Theory of Computation

A Pushdown Automata (PDA) is a finite automaton augmented with an auxiliary, unbounded stack for extra memory. Formally it is a 7-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, where $\Gamma$ is the stack alphabet, $Z_0$ the initial stack symbol, and $\delta$ maps a state, input symbol (or $ϵ$), and stack-top symbol to a set of (state, stack-string) pairs. The stack gives the PDA memory beyond what a finite set of states can encode, letting it count and match nested or paired structures. A PDA is the recognizer for exactly the context-free languages, and can accept either by reaching a final state or by emptying its stack, with the two acceptance modes being equivalent in power.