View source for Automaton

A [[Control system|control system]], which is usually understood to mean a finite automaton (cf. [[Automaton, finite|Automaton, finite]]) or one of its modifications obtained by changing components or the mode of operation. The principal concept — a finite automaton — originated in the mid-20th century in connection with attempts to describe, in mathematical language, the functioning of nervous systems, of universal computers and of other real automata. The first such efforts are due to W. McCulloch and W. Pitts (1943), S.C. Kleene (1951), A.W. Burks and J. Wright (1954), and others. A characteristic feature of such a description is the discrete character of the corresponding mathematical models and the finiteness of the domain of their parameter values, which accounts for the name  "finite"  automaton. The external effects, reactions and states are considered to be letters of three alphabets named, respectively, the input alphabet, the output alphabet and the alphabet of states. The relations governing their interactions may then be given by two functions — a transition function and an output function — which map the pair  "state-input letter"  into  "state letter"  and the pair  "state-output letter"  into  "output letter" , respectively. At each discrete moment of time the system, being in a given state, receives an input signal (a letter of the input alphabet), emits an output signal (a letter of the output alphabet, determined by the output function) and passes into a new state determined by the transition function. Studies of finite automata are supplemented by studies of their various generalizations and modifications which reflect various features of real systems. In the case of a finite automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141201.png" /> the existing modifications may be subdivided into the following three main groups. The first group includes automata some alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141202.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141203.png" /> of which are infinite, and such automata are said to be infinite. The second group includes automata in which the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141204.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141205.png" /> are replaced by arbitrary relationships or by random functions. These are partial, non-deterministic, probabilistic and other automata. The third group includes automata with specific sets of input objects. These are automata with a variable structure, automata over terms (or tree automata, cf. [[Automata, algebraic theory of|Automata, algebraic theory of]]). There are automata belonging to several groups at the same time, e.g. fuzzy automata belong to all three groups. Special subclasses of finite automata are very important; these include, for instance, memoryless automata, autonomous automata, reversible automata, etc. In addition, the use of concepts and methods of other branches of mathematics also generates specific classes of automata and related problems. For instance, if algebraic methods are employed there result the concepts of automata over terms, as well as linear, group, free and other automata (cf. [[Automata, algebraic theory of|Automata, algebraic theory of]]); problems in coding theory generate the concepts of self-regulating automata, reversible automata, etc. (cf. [[Automaton, probabilistic|Automaton, probabilistic]]). Structural automata also have several generalizations, mainly consisting in permitting infinite networks and altering the interconnections between the elements during the operation. This leads to the concept of a growing automaton. The principal modifications and subclasses of finite automata, together with their most important properties, are described below.

==Macro approach.==


1) Infinite automata (first group) differ from finite automata only by the fact that their alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141206.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141207.png" /> (input, output and set of states) may be infinite. Most concepts and problems connected with finite automata are naturally extended to infinite automata. Alphabets of higher cardinality extend the computational capacities of automata. For instance, while finite automata realize finitely-determined (sequential) functions (cf. [[Finitely-determined function|Finitely-determined function]]), infinite automata may be used to realize any determined function. Moreover, using infinite automata it is possible to describe the functioning of any automaton and machine. At the same time, this very general nature of infinite automata impairs their significance, so that most studies concern only special subclasses of infinite automata, connected with specific models of control systems.

2) Non-deterministic and asynchronous automata (second group). A non-deterministic automaton is formally defined as a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141208.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a0141209.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412010.png" /> are alphabets in the sense explained above, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412011.png" /> is a transition-to-output relation. If the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412012.png" /> is a function mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412013.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412014.png" />, the non-deterministic automaton is called a deterministic automaton and is in fact identical with a finite automaton, since in such a case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412015.png" /> may be considered as the pair of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412016.png" /> which map <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412017.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412019.png" />, respectively. As distinct from a finite automaton, an initialized non-deterministic automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412020.png" /> has several initial states, which form a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412021.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412022.png" />. The behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412023.png" /> is usually understood to mean one of the following generalizations of the behaviour of a finite automaton.

a) Instead of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412024.png" />, an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412025.png" /> realizes a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412026.png" />, consisting of all pairs of words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412027.png" /> such that there are states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412028.png" />, for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412030.png" /> is true for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412031.png" />. The class of relations realized by initialized non-deterministic automata coincides with the class of finitely-determined relations (cf. [[Finitely-determined function|Finitely-determined function]]).

b) An initialized non-deterministic automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412032.png" /> in which a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412033.png" /> of final states has been indicated, while the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412034.png" /> is empty (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412035.png" />), represents the event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412036.png" /> consisting of all words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412037.png" /> such that there are states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412038.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412041.png" /> is true for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412042.png" />. The class of events that can be represented by the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412043.png" /> is identical with the class of regular events, i.e. with respect to these aspects of their behaviour non-deterministic automata are equivalent to finite automata. However, the highly general nature of the concept of a non-deterministic automaton is reflected in the fact that a different number of states may be necessary to represent the same event using a non-deterministic automaton and using a finite automaton. There are events which are representable by a non-deterministic automaton with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412044.png" /> states and by a finite automaton with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412045.png" /> states, but not by any finite automaton with a smaller number of states.

A special subclass of non-deterministic automata is formed by the so-called partial automata, in which the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412046.png" /> is a partial function mapping the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412047.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412048.png" />, and which realize partial finitely-determined functions.

The term  "asynchronous automaton"  usually denotes one of the two following types of automata. The first type comprises automata of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412049.png" />, in which the output function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412050.png" /> maps the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412051.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412052.png" /> (for a finite automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412053.png" /> maps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412054.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412055.png" />). These automata are mainly used in coding theory. The second type comprises finite automata whose transition function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412056.png" /> has the following property: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412057.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412059.png" />. These automata are used in coding theory and also in modelling certain systems in technology and biology.

3) Automata with a variable structure (third group) are finite automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412060.png" /> with two input channels, together with some fixed infinite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412061.png" /> (a [[superword]]) in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412062.png" />. Arbitrary words in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412063.png" /> are sent to the first input (channel) of such an automaton, while initial segments of the same length of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412064.png" /> are sent to the second input (channel). This imposes a restriction on the set of pairs of input words. If the automaton with a variable structure is considered as an automaton having only the first input (into which any word of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412065.png" /> can be fed), its transition and its output functions will depend on the length of the input word which was fed in. In its behaviour, an automaton with a variable structure is equivalent to an infinite automaton with finite input and output alphabets and with a countable set of states.

4) Fuzzy automata constitute a generalization of the concept of a finite automaton, obtained by replacing the transition and output functions by fuzzy relations. A fuzzy subset of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412066.png" /> is defined as a function which maps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412067.png" /> into the segment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412068.png" />. Accordingly, in a fuzzy automaton, the transition and the output functions are replaced by functions mapping the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412070.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412071.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412072.png" /> is the set of states, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412073.png" /> is the input alphabet and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412074.png" /> is the output alphabet. The basic concepts and problems typical of finite automata have natural generalizations to fuzzy automata; this applies, in particular, to the representation of fuzzy events and the realization of fuzzy relations. Fuzzy automata are mathematical models for certain recognition mechanisms, and are used in [[Pattern recognition|pattern recognition]].

5) Special classes of finite automata.

Automata without memory are single-state finite automata or automata equivalent to them. In such automata each output letter is fully determined by the input letter which is fed in at that moment. Such automata are frequently referred to as functional elements and are extensively used in problems of synthesis of automata.

Automata with a finite storage space (or automata with a finite memory) are finite automata in which each output letter is fully determined by a bounded segment of the input word fed in during the preceding moments of time, irrespective of the initial state. For automata with a finite memory and with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412075.png" /> states the length of such a segment does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412076.png" />, and this maximum value is in fact attained for some automata. Automata with a finite memory are called self-regulating if, at a given time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412077.png" />, the output letter at any moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412078.png" /> is independent of the initial state. Such automata are used in coding theory (cf. [[Coding and decoding|Coding and decoding]]), and the modification of the automata usually employed in such cases satisfies the above condition not for the set of all input words, but only for some subset of this set. Automata with a finite memory are realized by logical networks without feedback.

Reverse automata or automata without loss of information are finite automata which realize one-to-one functions. Such automata are also used in coding theory.

==Micro-approach.==
There are three types of generalized structural automata, which may be considered as generalized logical networks: 1) generalized logical networks with a permanent structure, in which both the elements and the relation between them remain unchanged when the automaton is functioning; 2) generalized logical networks with a variable structure; and 3) generalized logical networks made of volume elements and connections. The main classes of such automata are described below.

1) Generalized logical networks with a permanent structure. These include mosaic structures and iterative networks, which are finite fragments of mosaic structures with a similar range of problems.

Mosaic structures are infinite unions of transition systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412079.png" /> (i.e. of finite automata of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412080.png" />, where the output function is identical with the transition function and the output alphabet is identical with the set of states). Such systems are placed at points with integer coordinates (integral points) of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014120/a01412081.png" />-dimensional space, while for each such point there is defined a finite set of integral points, called its neighbourhood. The input alphabet of the transition system placed at a certain point is the Cartesian product of the sets of states of the transition systems placed at the points in its neighbourhood.

A mosaic structure may be regarded as an infinite automaton whose input and output alphabets as well as its set of states are equal and are the infinite Cartesian product of the sets of states of all the transition systems contained in it. This makes it possible to reduce many problems for mosaic structures to problems for infinite automata. Problems specific to mosaic structures include modelling of effective procedures; in particular, of computational processes. Mosaic structures in which arbitrary automata instead of transition systems are used are also occasionally considered.

Uniform structures form an important class of mosaic structures. If all the transition systems are identical and if the neighbourhood of any point is obtained by a parallel translation of a certain fixed neighbourhood, the mosaic structure is known as a uniform structure or a cellular automaton. It is usually assumed, in this context, that there is some  "stable"  state of the transitional system, which is preserved if the input word is a tuple each term of which corresponds to this state. Typical problems on uniform structures are problems of self-reproduction and the  "Garden-of-Eden"  problem.

At any moment the states of the transition systems located at points in an integral lattice generate a kind of spatial mosaic pattern, which is usually denoted as a configuration. A configuration containing only a finite set of transition systems whose states are unstable (the excited part) is called finite. The self-reproduction problem consists of finding out whether finite configurations exist that, during the operation of the uniform system, pass into configurations, whose excited part is the multiply iterated excited part of the original configuration. The  "garden of EdenGarden of Eden"  is a term denoting a configuration which cannot result from configurations different from itself. The  "garden-of-Eden problemGarden-of-Eden problem"  is to determine the existence of  "Gardens of Eden"  for a given uniform structure.

2) Generalized logical networks with a variable structure. There exist various types of such logical networks. The most general ones include mosaic structures in which both the neighbourhoods of the elements and the elements themselves vary during the operation. As an example of such a generalized logical network one may mention the one-dimensional structure simulating the functioning of a [[Turing machine|Turing machine]] with input. In this case one of the nodes of the one-dimensional network corresponds to the control mechanism, while the other nodes correspond to the tape cells, which are considered as transition systems in which the letters of the working alphabet of the Turing machine serve as the input letters and states. The commutation is determined by the position of the head.

Another type of generalized logical networks with a variable structure are the so-called growing automata. They are uniform structures whose excited part increases during the operation. There are a number of models of such automata, which simulate various features of real mechanisms.

3) Generalized logical networks of volume elements are distinguished by the fact that a certain volume is assigned to their elementary automata and their mutual connections. As a result there arises the problem of synthesis of automata with minimum possible volume.

The term  "automaton"  is also used in concepts such as two-sided, multi-tape, multi-headed, linearly bounded, etc., automata, which are in fact modifications of the Turing machine. Sometimes all abstract machines are included in the concept of automata.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  W.S. McCulloch,   W. Pitts,   "A logical calculus of ideas immanent in nervous activity"  ''Bull. Math. Biophys.'' , '''5'''  (1943)  pp. 115–133</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.C. Kleene,   "Representation of events in nerve nets and finite automata" , ''Automata studies'' , '''34''' , Princeton Univ. Press  (1956)  pp. 3–41</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.W. Burks,   J.B. Wright,   "Sequence generators, graphs, and formal languages"  ''Inform. and Control'' , '''5'''  (1962)  pp. 204–212</TD></TR><TR><TD valign="top">[4a]</TD> <TD valign="top">  V.M. Glushikov,   "The abstract theory of automata"  ''Russian Math. Surveys'' , '''16''' :  5  (1961)  pp. 1–53  ''Uspekhi Mat. Nauk'' , '''16''' :  5  (1961)  pp. 3–62</TD></TR><TR><TD valign="top">[4b]</TD> <TD valign="top">  V.M. Glushikov,   ''Uspekhi Mat. Nauk'' , '''17''' :  2  (1962)  pp. 270</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  M.O. Rabin,   D. Scott,   "Finite automata and their decision problems"  ''IBM J. Res. Develop.'' , '''3'''  (1959)  pp. 114–125</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  L.A. Zadeh,   "Probability measures of fuzzy events"  ''J. Math. Anal. Appl.'' , '''23'''  (1968)  pp. 421–427</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V.Z. Alad'ev,   "On the theory of uniform structures" , Tallin  (1972)  (In Russian)</TD></TR></table>



====Comments====
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].