Automaton, finite

A mathematical model of a system with a finite memory which processes discrete information. Finite automata are one of the most important types of control systems (cf. Control system). Substantially, a finite automaton may be described as a system with input and output channels that is in one of states at any discrete moment of time. These moments constitute the time set. At each such moment signals — that is, letters from the input alphabet — are fed into the input channel and signals — that is, letters from the output alphabet — are produced by the output channel. Depending on the particular point of view, such system may include formal systems (cf. Formal system), real automata, living organisms, etc.

The concept of a finite automaton may be defined from different points of view. In the macro approach, i.e. when the only feature of interest is the external behaviour of the system, a finite automaton may be defined as a class of functions, as a finite oriented graph or (in algebraic form) as a finite algebra with unary operations (cf. Automata, methods of specification of). If the micro-approach is adopted, a finite automaton is defined as a set of elements and a scheme of their interconnections, i.e. not only the functioning of the automaton but also its structure is considered. This conception is accordingly known as structural, while the finite automata themselves are known as structural automata or automata networks.

Macro approach.

A finite automaton is a system where are finite alphabets, usually non-empty, known, respectively, as the input alphabet, the set of states and the output alphabet; is the transition function, which maps the set into ; is the output function, which maps into . Such finite automata are sometimes known as Mealy automata. If the output function maps into (i.e. is independent of the letters of the input alphabet), the finite automaton is known as a Moore automaton. Any Moore automaton is also a Mealy automaton.

The most important characteristic of a finite automaton is its behaviour (cf. Automaton, behaviour of an), which may be defined in different ways. Depending on the kind of behaviour under consideration, finite automata may be grouped into transformers, acceptors (identifiers), generators, etc. In order to define the main types of behaviour of finite automata, the functions and are extended to the set (where is the set of all words over , including the empty word ):

where while denotes the word obtained by adjoining the letter to the word . Thus, the extension of the functions and to arbitrary and describes, respectively, the state into which the automaton passes from the state under the effect of the input word , and the output letter which is produced by the automaton at the moment of entry of the last letter of the input word . Let denote the initial segment of length of the word , and let and be the words over and defined as follows:

The functions and describe the sequence of states assumed by the automaton during inputting the letters of the word , and also the output word, i.e. the sequence of letters of the output alphabet put out by the automaton when acted upon by the input word . The ternary relation

is known as the functioning (operation) of the finite automaton . The functions and are extended in a natural manner to infinite sequences (superwords) over . For this reason, the functioning of a finite automaton is sometimes understood to mean a relation of the type in which is an arbitrary superword. In such a case the value of the function is defined as the set of those and only those states which are encountered in the sequence an infinite number of times.

A finite automaton with a designated initial state is known as initialized and is denoted by . The behaviour of an initialized finite automaton is usually defined as one of the following four relations.

1) The function , which maps into (or into , where and are the sets of all superwords over and respectively). This function is called computable or realizable by the initialized finite automaton .

2) The set , which is defined for a given of the final states as follows:

The set is called an event representable by the finite automaton with set of final states.

3) The set of values of the function for all possible from , called the set enumerable by the given finite automaton .

4) The set , defined for a system of subsets of as follows:

The set is known as a super-event, representable by the finite automaton with a system of subsets of final states. Finite automata with behaviour of type 1) are known as finite transformers, while those with behaviour of type 2) are known as finite identifiers or acceptors.

If the Cartesian products and are taken as the input and output alphabets, respectively, behaviour of type 1) will be a tuple of functions of arguments. One says in such a case that the automaton has inputs and outputs, the alphabets and being called input and output alphabets of such an automaton, respectively. The class of events representable by a finite automaton and the class of functions computable by a finite automaton may be described by various mathematical tools. The principal result is that events representable by a finite automaton are identical with so-called regular events, while functions computable by a finite automaton are identical with finitely-determined functions (cf. Finitely-determined function). In addition, the class of sets enumerable by a finite automaton is identical with the class of events representable by a finite automaton.

Regarding behaviour of types 2), 3) and 4), Moore automata are equivalent to Mealy automata in the sense that to each Mealy automaton there corresponds an equivalent (i.e. displaying the same behaviour) Moore automaton, and vice versa. This is not true of behaviour of type 1). However, if in a Moore automaton functions of the form

are taken instead of , Moore automata will be equivalent to Mealy automata.

A Moore automaton is said to be an autonomous automaton, or a generator, if the transition function is independent of the letters of the input alphabet. The behaviour of an initialized autonomous automaton is usually understood to mean the superword

where . This sequence is periodic apart from a certain initial segment.

A finite automaton is said to be a transition system if and if, for any from , the equation is true, or if the output alphabet is empty. Thus, a transition system is completely defined by the three parameters .

The concepts of a finite automaton and functioning of a finite automaton may be defined by several equivalent methods (cf. Automata, methods of specification of; Automaton, behaviour of an). The so-called canonical equations are extensively employed. For any word let denote the -th letter of and let denote the length of . The functioning of a finite automaton will then comprise those and only those word triplets that satisfy the following conditions: 1) ; 2) for each such that the equalities , hold. To define the behaviour of an initialized finite automaton one must add the equality . The totality of these equalities unambiguously determines the behaviour of an initialized finite automaton, and is usually referred to as the canonical equations. Canonical equations are extensively employed in the analysis and synthesis of automata.

Micro-approach.

Figure: a014140a

Consider a set of elements consisting of a finite automaton as defined above with input and output alphabets of the form , where is a finite alphabet, identical for all elements. The construction rules of structural finite automata from these elements describe the permitted unions (identifications) of the inputs and outputs, and thus also define the input and output sets of the finite automaton thus obtained.

Figure: a014140b

The most important example of such finite automata are logical networks. One version of this concept is presented below. In this case and the elements are the so-called functional elements, which represent a finite automaton with a single state, and also certain special Moore automata, called delays. These are distinguished by the fact that they have two states, which are usually denoted by the letters 0 and 1 of the input alphabet, and that the transition and output functions satisfy the conditions and . Since functional elements have only one state, they are completely determined by the output function , which in this case is a Boolean function of arguments, where is the number of inputs of the functional elements. The elements themselves are initialized logical networks whose inputs and outputs correspond, respectively, to the inputs and outputs of the elements. Subsequent construction of more complex logical networks is performed according to the following rules.

1) The union of two logical networks is a logical network whose inputs and outputs are, respectively, those of the two logical networks (Fig. a).

2) The result of identifying two arbitrary inputs of a logical network is a logical network whose outputs are the same as those of the initial logical network and whose inputs are the same as those of the initial logical network, except for one of the identified inputs (Fig. b).

3) The result of connecting one output of a logical network to an input of another logical network is a logical network. Its inputs are all the inputs of the first logical network and those inputs of the second logical network that are not identified with the output of the first logical network; the outputs are all the outputs of both logical networks (Fig. c).

Figure: a014140c

4) The result of identification of the output of a logical network that is the output of a delay element with any input of the same logical network is a logical network whose inputs are all the inputs of the initial logical network except for the identified input, and whose outputs are all the outputs of the initial logical network (Fig. d). With certain restrictions this rule may also be applied to outputs that are not outputs of a delay element of a logical network.

Figure: a014140d

5) In any logical network it is possible to consider as output only some of the outputs as defined in 1–4 above. Logical networks obtained from functional elements by the rules 1, 2, 3 and 5 are usually said to be diagrams of functional elements.

The essential functioning of a logical network may be substantially described as follows. Let specified input letters be assigned to all inputs of the logical network at the moment and let the states of the delay elements be given. In this situation letters will be assigned to all inputs and outputs of the elements of the logical network, in particular to all outputs of the logical network, in accordance with the following rules. If the letters have been assigned to the inputs of a functional element with output function , the letter assigned to its output at this moment will be the value . If at the moment the delay is in state , the letter is assigned at the same moment to the output. Identical letters are assigned to identified inputs and outputs. Moreover, at the moment the states of the delay are determined by the input letters at the moment , as was stated above, i.e. . Thus, if the initial states of the delay are specified, the logical network defines a certain mapping of input sequences over the alphabet into output sequences over the alphabet , where is the number of inputs and is the number of outputs of the logical network. The class of such mappings is identical with the class of functions realized by finite automata in the first meaning of the word (i.e. with the class of finitely-determined functions), since the functioning of the logical network as described above is identical with the functioning of the finite automaton , where is the number of inputs, is the number of outputs of the logical network and is the Cartesian product of the sets of states of all delays in the logical network; the transition function is a coordinate-wise application of the transition functions of the delays, while the output function is determined in accordance with the functioning of functional elements and delay elements as described above.

For instance, let the elements consist of delays (marked as rectangles in Fig. e) and of functional elements with output functions and (marked as triangles with the respective symbols of the functions).

Figure: a014140e

Fig. eshows a logical network which, at the moment of time , outputs letter 1 if and only if the input letters at the moments contain an odd number of letters "1" (at the initial moment the delay has the value 0; letters and denote, respectively, the input and the output of the logical network). If and denote, respectively, the state, the input letter and the output letter at the moment , the functioning of such a logical network may be defined by the canonical equations:

If the macro-approach is adopted, this automaton can be represented in the form where , () and .

The concept of a finite automaton was the starting point of the modern theory of automata (cf. Automata, theory of), which is also concerned with various modifications and generalizations of this concept.

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]	N.E. Korbinskii, B.A. Trakhtenbrot, "Introduction to the theory of finite automata" , Moscow (1962) (In Russian)

Comments

See the Editorial Comments to the article Automata, equivalence of.