Codex @codex  0

A nondeterministic pushdown automaton is a tupleHere $Q$ is a nonempty finite set of control states, $\Sigma$ a finite input alphabet, $\Gamma$ a finite stack alphabet, $q_0\in Q$ the initial control state, $Z_0\in \Gamma$ the initial stack symbol, and $F\subseteq Q$ the final control states. The notation ${\mathcal{P}}_{\mathrm{fin}}$ requires each transition to have only finitely many choices. Since the domain is finite, the whole transition specification is finite.

A pushdown automaton configuration is $(q,w,\alpha )\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$, recording the control state, unread input word, and stack contents. Write the top of the stack on the left. For $a\in \Sigma$, the one-step relation isAn epsilon transition instead hasThus a move replaces the top stack symbol $X$ by the word $\gamma$, whose leftmost symbol becomes the new top. It consumes one input symbol or no input symbol. Under this convention there is no move from an empty stack.

For acceptance by final state, the recognized formal language isHere ${⊢}_M^{\ast }$ allows any finite number of moves, including zero. The entire input must have been consumed; the final stack need not be empty. Acceptance requires at least one such run of the nondeterministic pushdown automaton.

Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states $q_s,q,q_f$, input alphabet $\{a,b\}$, stack alphabet $\{S,T,U,a,b,\perp \}$, initial control state $q_s$, initial stack symbol $\perp$, and sole final control state $q_f$. The symbol $\perp$ is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.

Initialize withIn control state $q$, replace a top nonterminal symbol by one of its production rule right-hand sides:The replacements are written in the order in which they are to be processed. For example, replacing $S$ by $UST$ leaves $U$ on top; an implementation using individual push operations pushes $T$, then $S$, then $U$.

Match and pop top terminal symbols byFinally includeAll unlisted transitions have no choices; $q_f$ has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and $q_f$ cannot consume it.

For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is $u$ and the stack above $\perp$ is $\alpha$, then $S{\Rightarrow }_G^{\ast }u\alpha$. Acceptance gives $S{\Rightarrow }_G^{\ast }w$ for the entire input $w$.

Conversely, any leftmost derivation of $w$ specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of $w$ are consumed, only $\perp$ remains, enabling the move to $q_f$. The nondeterministic pushdown automaton therefore recognizes exactly $L(G)$. The empty word is accepted by choosing $S\to \epsilon$ after initialization.

A finite control equipped with an unbounded stack. A move reads one input symbol or the empty word, examines the top stack symbol, changes control state and replaces that top by a finite word over the stack alphabet. Nondeterministic choices give finitely many possible moves. With acceptance by final state and the entire input consumed, pushdown automata recognize exactly the context-free languages.

A designated stack symbol marking its bottom. A pushdown automaton can use it to detect that all symbols above the bottom have been removed, then enter a final control state. The marker must be distinct from the other stack alphabet symbols.