Automata

Automata are abstract machines used to model computation and formal languages. An automaton consists of a set of states, an input alphabet, a transition function, a designated start state, and one or more accepting states. It processes an input string by moving through states; if the final state is accepting, the input is accepted, otherwise it is rejected.

Finite automata have a finite number of states and can be deterministic or nondeterministic. They recognize the regular languages. Pushdown automata add a stack and can recognize context-free languages. Linear-bounded automata constrain memory to a portion of the input and recognize context-sensitive languages. Turing machines, the most general model, can simulate any algorithm.

These models are organized in the Chomsky hierarchy: regular, context-free, context-sensitive, and recursively enumerable languages. The hierarchy helps classify problems and languages; proofs often use techniques such as the pumping lemma for regular and context-free languages.

Automata theory originated in the work on formal languages in the mid-20th century, with contributions from Kleene, Rabin and Scott, and Turing. Practical applications include lexical analysis and parsing in compilers, text processing, protocol verification, and model checking in software and hardware systems.

Automata also clarify fundamental limits of computation. Decidability results, such as the halting problem and Rice's theorem, show that many questions about programs and languages cannot be resolved algorithmically.