CS 231:Automata Theory

Automata Theory-Automata are abstract mathematical models of machines that perform computations on an input by moving through a series of states or configurations. If the computation of an automaton reaches an accepting configuration it accepts that input. At each stage of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration.
Turing machines are the most general automata. They consist of a finite set of states and an infinite tape which contains the input and is used to read and write symbols during the computation. Since Turing machines can leave symbols on their tape at the end of the computation, they can be viewed as computing functions: the partial recursive functions. Despite the simplicity of these automata, any algorithm that can be implemented on a computer can be modeled by some Turing machine.
Turing machines are used in the characterization of the complexity of problems. The complexity of a problem is determined by the efficiency of the best algorithm that solves it. Measures of an algorithm's efficiency are the amount of time or space that a Turing machine requires to implement the algorithm. A computation's time is the number of configurations involved in that computation, and its space corresponds to the number of positions on its tape that were used.
Automata theory has close ties to formal language theory, since there is a correspondence between certain families of automata and classes of languages generated by grammar formalisms. A language is accepted by an automaton when it accepts all of the strings in the language and no others. The family of Turing machines accept exactly the class of languages produced by Type 0 grammars. Turing machines whose space cannot be more than that occupied by the input (linear-bounded) accept the class of languages generated by context-sensitive (Type 1) grammars. The most restricted family of automata are finite automata consisting of only a finite number of states and a "read-only" tape containing the input to be read in one direction. Finite automata recognize the class of languages generated by regular (Type 3) grammars. These automata can be given a limited amount of extra power with the addition of certain forms of storage. For example, pushdown automata involve a pushdown store: a sequence in which symbols can only be added and removed from one end, with the effect that the first symbols in, are the last ones out. Pushdown automata accept the languages generated by context-free (Type 2) grammars.
Automata theory gave rise to the notion of deterministic computation, hence deterministic languages. In a deterministic computation each configuration of the machine has only one possible successor. For some families of automata (e.g., finite automata and Turing machines) deterministic and nondeterministic automata are equivalent. For others (e.g., pushdown automata) there are languages that can be accepted by a non-deterministic automata of that family but cannot be accepted by any deterministic automata.
In theoretical computer science, automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata.

Automata	Recognizable language
Deterministic finite automata (DFA)	regular languages
Nondeterministic finite automata (NFA)	regular languages
Nondeterministic finite automata with ε-transitions (FND-ε or ε-NFA)	regular languages
Pushdown automata (PDA)	context-free languages
Linear bounded automata (LBA)	context-sensitive language
Turing machines	recursively enumerable languages
Timed automata
Deterministic Büchi automata	ω-limit languages
Nondeterministic Büchi automata	ω-regular languages
Nondeterministic/Deterministic Rabin automata	ω-regular languages
Nondeterministic/Deterministic Streett automata	ω-regular languages
Nondeterministic/Deterministic parity automata	ω-regular languages
Nondeterministic/Deterministic Muller automata	ω-regular languages

The figure at right illustrates a finite state machine, which is one well-known variety of automaton. This automaton consists of states (represented in the figure by circles), and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs).
Automata theory is also closely related to formal language theory, as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set.

An example of automata and study of mathematical properties of such automata is automata theory

 

A theory concerned with models (automata) used to simulate objects and processes such as computers, digital circuits, nervous systems, cellular growth, and reproduction. Automata theory helps engineers design and analyze digital circuits which are parts of computers, telephone systems, or control systems. It uses ideas and methods of discrete mathematics to determine the limits of computational power for models of existing and future computers. Among many known applications of finite automata are lexical analyzers and hardware controllers.
The concept now known as the automaton was first examined by A. M. Turing in 1936 for the study of limits of human ability to solve mathematical problems in formal ways. His automaton, the Turing machine, is too powerful for simulation of many systems. Therefore, some more appropriate models were introduced.

Turing machines and intermediate automata

The Turing machine is a suitable model for the computational power of a computer. A Turing machine has two main parts: a finite-state machine with a head, and a tape (see illustration). The tape is infinite in both directions and is divided into squares. The head sees at any moment of time one square of the tape and is able to read the content of the square as well as to write on the square. The finite-state machine is in one of its states. Each square of the tape holds exactly one of the symbols, also called input symbols or machine characters. It is assumed that one of the input symbols is a special one, the blank, denoted by B.

Turing machine. (a) General idea. (b) An example of a computation.

At any moment of time, the machine, being in one of its states and looking at one of the input symbols in some square, may act or halt. The action means that, in the next moment of time, the machine erases the old input symbol and writes a new input symbol on the same square (it may be the same symbol as before, or a new symbol; if the old one was not B and the new one is B, the machine is said to erase the old symbol), changes the state to a new one (again, it is possible that the new state will be equal to the old one), and finally moves the head one square to the left, or one square to the right, or stays on the same square as before.
For some pairs of states and input symbols the action is not specified in the description of a Turing machine; thus the machine halts. In this case, symbols remaining on the tape form the output, corresponding to the original input, or more precisely, to the input string (or sequence) of input symbols. A sequence of actions, followed by a halt, is called a computation. A Turing machine accepts some input string if it halts on it. The set of all accepted strings over all the input symbols is called a language accepted by the Turing machine. Such languages are called recursively enumerable sets.
Another automaton is a nondeterministic Turing machine. It differs from an ordinary, deterministic Turing machine in that for a given state and input symbol, the machine has a finite number of choices for the next move. Each choice means a new input symbol, a new state, and a new direction to move its head.
A linear bounded automaton is a nondeterministic Turing machine which is restricted to the portion of the tape containing the input. The capability of the linear bounded automaton is smaller than that of a Turing machine.
A computational device with yet smaller capability than that of a linear bounded automaton is a push-down automaton. It consists of a finite-state machine that reads an input symbol from a tape and controls a stack. The stack is a list in which insertions and deletions are possible, both operations taking place at one end, called the top. The device is nondeterministic, so it has a number of choices for each next move. Two types of moves are possible. In the first type, a choice depends on the input symbol, the top element of the stack, and the state of the finite-state machine. The choice consists of selecting a next state of the finite-state machine, removing the top element, leaving the stack without the top element, or replacing the top element by a sequence of symbols. After performing a choice, the input head reads the next input symbol. The other type is similar to the first one, but now the input symbol is not used and the head is not moved, so the automaton controls the stack without reading input symbols. See also Abstract data type.

Finite-state machines

A finite-state automaton, or a finite-state machine, or a finite automaton, is a computational device having a fixed upper bound on the amount of memory it uses (unlike Turing and related machines). One approach to finite automata is through the concept of an acceptor. The finite automaton examines an input string (that is, a sequence of input symbols, located on the tape) in one pass from left to right. It has a finite number of states, among which one is specified as initial. The assumption is that the finite automaton starts scanning of input standing in its initial state. Some of the states are called accepting states. The finite automaton has a transition function (or next-state function) which maps each state and input symbol into the next state. In each step the finite automaton computes the next state and reads the next input symbol. If after reading the entire input string the last state is accepting, the string is accepted; otherwise it is rejected.