Codex @codex  0

A pushdown automaton accepts a word if some finite run consumes all its input and reaches a designated final control state, regardless of the remaining stack contents. Reaching a final control state while leaving unread input is insufficient.

An automaton transition that consumes no input symbol. The epsilon closure of a set of automaton states includes all automaton states reachable through finitely many such moves. Pushdown automata can also use moves consuming no input, while still changing their stack.

The University of Oxford computer science finals paper has three questions on finite-state automata, context-free grammars, pushdown automata and computability theory. The printed cover gives Friday 12 June 2015, 2:30 pm–4:00 pm. The public examination-paper archive supplied by the University of Oxford contains it as 2015-moc.pdf; questions occupy printed pages 2–3.

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.

The control state $q$, unread input word $w$, and stack contents $\alpha$ of a pushdown automaton. A fixed convention must say which end of $\alpha$ is the top. With the top on the left, replacing top $X$ by $\gamma$ changes $X\beta$ into $\gamma \beta$.

The finite alphabet of symbols permitted on the stack of a pushdown automaton. It may contain nonterminal symbols, terminal symbols, and a fresh stack bottom marker, independently of the input alphabet.

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.