Automata are abstract machines that are studied in theoretical computer science. They are abstract in the sense that they embody an idealized or imaginary form of computation that could be constructed in many ways. The primary application of automata is as symbol processors, that is, they process information presented to them as a string of symbols drawn from a fixed alphabet.

The simplest of these is the finite-state automaton, which consists of a set of states and a list of rules. At any point in time the finite-state automaton is in one state (called the current state), and responds to one symbol of its input (called the current symbol). Each rule specifies for each state and each possible input symbol which new state the automaton will move to. The finite-state automaton begins in a specified initial state. The current state and the current input symbol are...