Automata, theory of

A branch of the theory of control systems whose subject is the study of mathematical models of transformers of discrete information, known as automata. In a sense, such transformers may be both real mechanisms (computers, automata, living organisms, etc.) and abstract systems (mathematical machines, axiomatic theories, etc.). The theory of automata was born in the mid-20th century in connection with finite automata (cf. Automaton, finite), which are mathematical models of nervous systems and electronic computers. The class of objects and the scope of problems dealt with by the theory of automata was subsequently enlarged, and came to include certain concepts in and problems of other branches of mathematics. The theory of automata is most closely connected with the theory of algorithms (cf. Algorithms, theory of), particularly so with the theory of abstract machines, since automata can be regarded as a special case of such machines.

Most problems of the theory of automata are similar to those of the other main types of control systems. They include the problems of analysis and synthesis of automata, completeness problems, minimization problems, problems on equivalent transformations of automata, etc. The problems of analysis concern the description of the behaviour of a given automaton or the determination of certain of its properties from its behaviour and from given incomplete data on its behaviour (cf. Automaton, behaviour of an; Automata, experiments with). Problems in the synthesis of automata include the construction of automata with pre-defined properties or automata functioning in a desired manner (cf. Synthesis problems). Related problems concern estimates of the complexity of automata behaving in a given manner and the construction of automata which are, in some sense, optimal (cf. Automata, minimization of). In addition, there arises the problem of completeness in connection with classes of initialized automata or mappings of automata (cf. Functional system; Automata, complete systems of). The problem of equivalent transformations may be posed both for automata and in various problems concerning their behaviour (cf. Equivalent transformations). In addition to problems of the above type, which are common to many control systems, there are problems specific to automata. Thus, depending on the particular problem at hand, it may be convenient to specify the behaviour of automata in various languages (regular expressions, canonical equations, language of logical predicates, etc., cf. Automata, methods of specification of), which gives rise to problems concerning the choice of an adequate and convenient language, and concerning the translation from one language to another. Other problems, closely connected with synthesis and equivalent transformation problems, is the problem of minimization of the number of states of an automaton and that of obtaining corresponding estimates. Fairly simple algorithms have been developed for finite automata making it possible, with the aid of regular expressions, to obtain automata with the minimum possible number of states and representing appropriate events (cf. Automata, minimization of). A related set of problems concerns the modelling of the behaviour of automata in one class by automata in another class. Problems of the minimization of modelling automata and estimation of their complexity are also of interest. For instance, on passing from a non-deterministic automaton (source) representing (generating) a regular set of words to a finite automaton representing the same set, the number of states may increase exponentially. A special field of the theory of automata are the so-called experiments with automata (cf. Automata, experiments with). Here, the principal problem is to obtain certain information about the structure of an automaton by observing its reactions to certain outside effects. This involves a wide circle of problems concerning the classification of experiments and problem-solving by certain kinds of experiments, as well as estimates of the shortest experiment sufficient to solve a given problem. The concept of experiments with automata is also used in control problems concerning automata (cf. Reliability and inspection of control systems). Problems of the interaction of automata — either with each other or with given external environments — are dealt with in branches dealing with automaton games and the behaviour of automata (cf. Automaton, behaviour of an). Many of these problems may be considered as being algorithmic in nature. Most of them have a positive solution for finite automata.

The theory of automata has found applications both in other branches of mathematics and in solving practical problems. Thus, it can be used to prove the solvability of certain formal calculi. The application of the methods and concepts of the theory of automata to the study of formal and natural languages gave rise to a special branch of the theory of algorithms: mathematical linguistics. The concept of an automaton can serve as model in a great variety of problems, and can thus be employed in many studies, both in pure and applied sciences.

References

[1]	C.E. Shannon (ed.) J. McCarthy (ed.) , Automata studies , Princeton Univ. Press (1956)
[2]	V.M. Glushkov, "Synthesis of numerical automata" , Moscow (1962) (In Russian)
[3]	B.A. Trakhtenbrot, Ya.M. Bardzdin', "Finite automata. Behaviour and synthesis" , North-Holland (1973)

Comments

This article refers to only some aspects of the theory. One should also consult the articles Formal languages and automata; $ L $- systems; Complexity theory.