Acceptance by final state 2026-10-31
Automata theory 2026-11-05
Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.
For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per and pop once per . These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.
Epsilon transition 2026-10-31
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.
Formal language theory Created 2026-09-24 Updated 2026-11-05
Formal language theory studies sets of finite strings over a specified alphabet, and the grammars or machines that describe them. A formal language can be finite, such as , or infinite, such as all binary strings with an even number of ones.
A finite-state machine recognizes the latter using only two states, recording parity. By contrast, the language needs an unbounded counting mechanism and is recognized by a pushdown automaton, but not by any finite-state recognizer. Comparing these classes explains which memory resources a pattern requires and connects grammar design to computability theory.
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. Pushdown automaton 2026-10-31
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.
Pushdown automaton configuration 2026-10-31
The control state , unread input word , and stack contents of a pushdown automaton. A fixed convention must say which end of is the top. With the top on the left, replacing top by changes into .
Stack alphabet 2026-10-31
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.
Stack bottom marker 2026-10-31
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.