Automata theory

Automata theory explores abstract machines—called automata—and the computational problems they can solve. It belongs to theoretical computer science and has strong ties to cognitive science and mathematical logic. The word "automata" comes from the Greek *αὐτόματος*, meaning "self-acting, self-willed, self-moving." An automaton (plural: automata) is an abstract, self-propelled computing device that follows a predetermined sequence of operations automatically. A finite automaton (FA), also known as a finite-state machine (FSM), has a finite number of states. In such a machine, states are represented by circles and transitions by arrows. When the automaton reads an input symbol, it moves—or transitions—to another state based on a transition function that uses the previous state and the current input symbol.

This field is closely linked to formal language theory. Automata serve as finite representations of formal languages, which may be infinite. They are often classified by the types of formal languages they can recognize, as seen in the Chomsky hierarchy, which nests major classes of automata. Automata are important in the theory of computation, compiler construction, artificial intelligence, parsing, and formal verification.

The theory of abstract automata took shape in the mid-20th century, initially as a branch of mathematical systems theory focused on discrete-parameter systems. Early work differed from earlier systems research by using abstract algebra to describe information systems, rather than differential calculus for material systems. The finite-state transducer was developed under various names by different research communities. The earlier concept of the Turing machine was also incorporated, along with new infinite-state automata like pushdown automata.

In 1956, the volume *Automata Studies* was published, collecting work from scientists including Claude Shannon, W. Ross Ashby, John von Neumann, Marvin Minsky, Edward F. Moore, and Stephen Cole Kleene. With this publication, automata theory became a relatively autonomous discipline. The book included Kleene’s description of regular events (or regular languages) and Shannon’s relatively stable measure of complexity in Turing machine programs. That same year, Noam Chomsky introduced the Chomsky hierarchy, a correspondence between automata and formal grammars, and Ross Ashby published *An Introduction to Cybernetics*, an accessible textbook using basic set theory to explain automata and information.

Research on linear bounded automata led to the Myhill–Nerode theorem, which provides a necessary and sufficient condition for a formal language to be regular and gives an exact count of states in a minimal machine for that language. The pumping lemma for regular languages, useful for proving regularity, was also proven during this period by Michael O. Rabin and Dana Scott, along with the computational equivalence of deterministic and nondeterministic finite automata.

In the 1960s, a body of algebraic results known as "structure theory" or "algebraic decomposition theory" emerged. This dealt with realizing sequential machines by interconnecting smaller machines. While any finite automaton can be simulated using a universal gate set, such simulation requires circuits with arbitrarily complex loops. Structure theory focused on "loop-free" realizability of machines. The theory of computational complexity also developed in the 1960s. By the end of the decade, automata theory was seen as "the pure mathematics of computer science."

An automaton runs when given a sequence of inputs in discrete time steps. It processes one input at a time from a set of symbols called the input alphabet. The sequence of symbols received is called a word. The automaton has a set of states, and at each moment it is in one of them. When it receives new input, it transitions to another state based on a transition function that uses the previous state and current input symbol. An output function simultaneously produces symbols from the output alphabet, also based on the previous state and current input. The automaton reads the input word and transitions between states until the word is fully read (if finite), at which point it halts. The state where it halts is called the final state.

To study state, input, and output sequences using formal language theory, a machine is given a starting state and a set of accepting states. Depending on whether a run starting from the starting state ends in an accepting state, the automaton accepts or rejects the input sequence. The set of all words accepted by an automaton is its recognized language. A familiar example is an electronic lock, which accepts or rejects attempts to enter the correct code.