Automata theory

Automata theory studies abstract machines, the languages they recognize, and the limits of their computational power. It connects models of computation with formal language theory.

Finite-state machine: A machine with finitely many states that changes state in response to inputs. Finite-state machines are the basic models behind the simplest automata and regular languages.
Nondeterministic finite automaton: A finite automaton that may have multiple possible transitions for an input and state. Nondeterminism offers a flexible description of regular-language recognition.
Computability theory: The study of which problems can be solved by algorithms and which cannot. Turing-machine automata provide the central model for defining algorithmic solvability.
Alan Turing: A British mathematician whose work established foundational ideas in computation and artificial intelligence. His abstract machine model became the standard account of general computation.
Finite automaton: A state machine with finite memory that recognizes regular languages. It contrasts with stack and tape machines whose additional memory expands recognition power.
Formal language: A set of finite strings over an alphabet. Automata are commonly classified by the formal languages they recognize.
Deterministic finite automaton: A finite automaton with exactly one next state for each state and input symbol. Deterministic machines provide a direct, step-by-step account of recognition.
Decidability: The property of a problem having an algorithm that always terminates with the correct answer. Automata models distinguish decidable language questions from undecidable ones.
Alonzo Church: An American mathematician who developed lambda calculus and results on undecidability. Church's formalism and thesis developed alongside Turing's account of computability.
Linear bounded automaton: A Turing machine whose usable tape is bounded by a linear function of input length. It occupies an intermediate power level between pushdown and unrestricted Turing machines.

Linked from 6 pages