title: "Pushdown Automaton"

Pushdown Automaton

Definition. A pushdown automaton (PDA) is a six-tuple $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$ where $Q$, $\Sigma$, $q_0$, and $F$ are as in an NFA, $\Gamma$ is the stack alphabet, and $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))$.

A PDA is an NFA with a stack: each move may consume an input symbol, pop a stack symbol, and push a stack symbol, any of which may be skipped. The stack holds unboundedly much information but only its top is reachable, which is exactly the memory needed to match nested structure. Unlike the DFA and NFA, which the subset construction proves equivalent, deterministic PDAs are strictly weaker than nondeterministic ones; the even-length palindromes separate them. Defined in Lecture 5.