Automata, methods of specification of

The various ways of describing automata and their functioning or behaviour. The method of specification of an automaton will depend on the approach to the concept of an automaton. If the macro-approach is adopted (cf. Automaton, finite), it is the external behaviour of an automaton which is described. If the micro-approach is adopted, the definition should include a description of the elements from which the automaton is constructed, and the schemes of their composition (cf. Automata, composition of). Methods of specifying finite automata are described below.

Macro-approach.

To specify a finite automaton $ \mathfrak A = \langle A, S, B, \phi , \psi \rangle $ for given alphabets $ A = \{ a _ {1} \dots a _ {m} \} $, $ S = \{ s _ {1} \dots s _ {n} \} $ and $ B = \{ b _ {1} \dots b _ {k} \} $ is tantamount to describing the functions $ \phi $ and $ \psi $ or to describing the behaviour of this automaton (cf. Automaton, behaviour of an). The functions $ \phi $ and $ \psi $ are often defined by means of a table, a diagram or a matrix of transitions. The table of transitions $ T $ of the automaton $ \mathfrak A $ consists of two subtables $ T _ \phi = \| t _ {ij} ^ \phi \| $ and $ T _ \psi = \| t _ {ij} ^ \psi \| $, $ i=1 \dots n $, $ j=1 \dots m, $ $ t _ {ij} ^ \phi \in S $, $ t _ {ij} ^ \psi \in B $. The functions $ \phi $ and $ \psi $ are defined by $ \phi ( s _ {i} , a _ {j} ) = t _ {ij} ^ \phi $, $ \psi ( s _ {i} , a _ {j} ) = t _ {ij} ^ \psi $. If all the columns of $ T _ \psi $ coincide, the table $ T $ defines a Moore automaton. For instance, let $ A _ {0} = \{ a _ {1} , a _ {2} \} $, $ S _ {0} = \{ s _ {1} , s _ {2} \} $, $ B _ {0} = \{ b _ {1} , b _ {2} \} $; the table $ T $( Fig. a) will then specify the functions $ \phi _ {0} $ and $ \psi _ {0} $ of some automaton $ \mathfrak A ^ {0} $( Fig. bshows the subtables $ T _ \phi $ and $ T _ \psi $ of $ T $).

Figure: a014060a

Figure: a014060b

The diagram of (transitions of) an automaton is an oriented graph $ G $ with a one-to-one correspondence between the vertices of the graph and the elements of $ S $, and between the edges of the graph and certain sets of pairs of the form $ (a, b) $, $ a \in A $, $ b \in B $. Each vertex of $ G $ is the starting point of at least one edge, and the set $ \mathfrak N $ of all pairs assigned to the edges with the same vertex as their origin has the form $ \mathfrak N = \{ (a _ {1} , b _ {i _ {1} } ) \dots ( a _ {m} , b _ {i _ {m} } ) \} $. The functions $ \phi $ and $ \psi $ are then defined as follows: $ \phi ( s _ {i} , a _ {j} ) = s _ {r} $, $ \psi ( s _ {i} , a _ {j} ) = b _ {p} $ if the pair $ ( a _ {i} , b _ {p} ) $ is assigned to the edge issuing from from $ s _ {i} $ and if this edge ends in the vertex $ s _ {r} $. It is convenient to formulate certain properties of automata in the language of diagrams (connectivity of an automaton, attainability of states, etc.). Fig. c shows the transition diagram of the automaton $ \mathfrak A ^ {0} $.

Figure: a014060c

The transition matrix is used to describe the functioning of the transition system $ \langle A, S, \phi \rangle $( cf.Automaton, finite). It is represented by the $ (n \times n) $- matrix $ P = \| P _ {ij} \| $ whose elements are subsets of the alphabet $ A $( including the empty subset) such that $ a \in P _ {ij} $ if and only if $ \phi (s _ {i} , a) = s _ {j} $, so that for any $ i = 1 \dots n $ the relations $ P _ {ip} \cap P _ {ir} = \emptyset $ if $ p \neq r $ and $ \cup _ {j=1} ^ {n} P _ {ij} = A $ are true. In order to extend the function $ \phi $ to the set $ S \times A ^ {*} $( where $ A ^ {*} $ is the set of all words over the alphabet $ A $ including the empty word), one considers the sequence of powers of the matrix $ P $. Multiplication of $ P $ by itself is carried out by the usual algorithm, using the operations of concatenation and union of word sets instead of multiplication and addition. If $ \alpha \in A ^ {*} $ is a word of length $ d $ and $ \alpha \in P _ {ij} ^ {(d)} $ where $ P _ {ij} ^ {(d)} $ is an element of the matrix $ P ^ {d} $, one has $ \phi (s _ {i} , \alpha ) = s _ {j} $. Thus, the transition matrix $ P $ of the transition system $ \langle A _ {0} , S _ {0} , \phi _ {0} \rangle $ and the matrix $ P ^ {2} $ have, respectively, the forms:

$$ P = \ \left \| \begin{array}{cc} a _ {1} &a _ {2} \\ a _ {2} &a _ {1} \\ \end{array} \right \| , $$

$$ P ^ {2} = P \times P = \left \| \begin{array}{cc} \{ a _ {1} a _ {1} , a _ {2} a _ {2} \} &\{ a _ {1} a _ {2} , a _ {2} a _ {1} \} \\ \{ a _ {2} a _ {1} , a _ {1} a _ {2} \} &\{ a _ {2} a _ {2} , a _ {1} a _ {1} \} \\ \end{array} \right \| . $$

A number of minimization (reduction) algorithms and algorithms of automaton synthesis are associated with these methods of specifying automata.

In order to specify the behaviour of an initialized (not necessarily finite) automaton $ \mathfrak A _ {s _ {1} } $( transformer), one must define the function $ f ( \alpha ) = \psi ( s _ {1} , \alpha ) $ which maps $ A ^ {*} $ into $ B ^ {*} $( or $ A ^ \infty $ into $ B ^ \infty $, where $ A ^ \infty , B ^ \infty $ are the sets of all the superwords over the alphabets $ A $ and $ B $, respectively).

Figure: a014060d

This function may be defined by means of an information tree. From each vertex of the information tree there issue $ m $ edges, which are in one-to-one correspondence with the respective letters of $ A $. To each vertex is assigned a state of the automaton $ \mathfrak A _ {s _ {1} } $, while to each edge is assigned a letter of $ B $ in the following way. The state $ s _ {1} $ is assigned to the root. If the state $ s _ {i} $ has been assigned to some vertex, the letter $ b = \psi (s _ {i} , a) $ is assigned to the edge corresponding to the letter $ a $ from $ A $, while to the vertex in which this edge terminates the state $ s _ {j} = \phi (s _ {i} , a) $ is assigned. To each word $ \alpha = \alpha _ {1} \dots \alpha _ {r} \in A ^ {*} $ corresponds a unique sequence $ \rho = \rho _ {1} \dots \rho _ {r} $ of edges of this tree such that $ \rho _ {1} $ issues from the root and $ \rho _ {i+1} $ issues from the vertex of termination of $ \rho _ {i} $. The word $ \beta = \beta _ {1} \dots \beta _ {r} $, where $ \beta _ {i} $ is the letter from $ B $ assigned to the edge $ \rho _ {i} $, $ i = 1 \dots r $, is identical with the value $ \overline \psi \; (s _ {1} , \alpha ) $. If the function $ f $ is realized by a finite automaton, the corresponding information tree may be effectively determined by means of a finite subtree. Fig. d shows the subtree of the initialized automaton $ \mathfrak A _ {s _ {1} } ^ {0} $( the left-hand edges, issuing from the vertices, correspond to the symbol $ a _ {1} $, while the right-hand edges correspond to the symbol $ a _ {2} $).

The behaviour of a finite automaton (acceptor) in terms of a representable event (super-event) may be effected with the aid of a regular expression (cf. Regular event). Such events may also be specified as sets of words generated (derived) in some formal system (a semi-Thue grammar, etc.). In this case the semi-Thue system is given as the quadruple $ T = \langle A, S, \xi , \omega \rangle $ where $ A, S $ are finite alphabets, $ A \cap S = \emptyset $, $ \xi $ is an axiom scheme of the form $ s _ {0} X $ and $ \omega $ is the set of schemes of derivation rules of the form $ saX \rightarrow s ^ \prime X $, $ r \rightarrow r $, where $ s, s ^ \prime , r \in S $, $ a \in A $ and $ X $ is a variable which assumes values from $ A ^ {*} $. If, moreover, $ saX \rightarrow s ^ \prime X $ and $ saX \rightarrow s ^ {\prime\prime} X $ belong to $ \omega $, one has $ s ^ \prime = s ^ {\prime\prime} $. The word $ \alpha \in A ^ {*} $ is deducible in the system $ T $ if there exists a sequence of words $ s _ {0} \alpha = w _ {1} \dots w _ {n} $ such that $ w _ {i+1} $ is obtained from $ w _ {i} $, $ i = 1 \dots n - 1 $, by the application of a certain rule from $ \omega $, $ w _ {n} \in S $ and $ \omega $ does not contain the rule $ w _ {n} \rightarrow w _ {n} $. A grammar generating a regular event has a similar form. It is given by the quadruple $ \Gamma = (A, S, s _ {1} , \omega ) $ where $ s _ {1} $ from $ S $ is an axiom, $ \omega $ is the set of rules of the form $ s _ {i} \rightarrow as _ {j} $ or $ s _ {i} \rightarrow a $. The word $ \alpha = \alpha _ {1} \dots \alpha _ {n} $ is deducible in $ \Gamma $ if $ \omega $ includes the rules $ s _ {1} \rightarrow \alpha _ {1} s _ {i _ {2} } $, $ s _ {i _ {2} } \rightarrow \alpha _ {2} s _ {i _ {3} } \dots s _ {i _ {n} } \rightarrow \alpha _ {n} $. Algorithms which yield the transition matrix of an automaton from formal schemes of this type are known. Thus, an event represented in the acceptor $ \langle A _ {0} , S _ {0} , \phi _ {0} , s _ {1} \rangle $ by the state $ s _ {2} $ may be defined, for example, as the set of words that are deducible in the semi-Thue system

$$ {\mathcal T} = \langle A _ {0} , S _ {0} , \xi = \{ s _ {1} X \} , $$

$$ \omega = \{ s _ {1} a _ {2} X \rightarrow s _ {2} X ; s _ {1} a _ {1} X \rightarrow s _ {1} X ; $$

$$ {}{}s _ {2} a _ {1} X \rightarrow s _ {2} X ; s _ {2} a _ {2} X \rightarrow s _ {1} X ; s _ {1} \rightarrow s _ {1} \} \rangle. $$

There exist several other ways of specifying an automaton. For instance, a (necessarily finite) transition system $ \langle A, S, \phi \rangle $ may be specified as an algebra $ \langle S, \Phi \rangle $ where $ \Phi = \{ {\phi _ {a} } : {a \in A } \} $ is the set of unary operations on $ S $ such that $ \phi _ {a} (s) = \phi (a, s) $. Thus, the transition system $ \langle A _ {0} , S _ {0} , \phi _ {0} \rangle $ may be regarded as the algebra $ \langle S _ {0} , \{ \phi _ {a _ {1} } , \phi _ {a _ {2} } \} \rangle $, where $ \phi _ {a _ {1} } ( s _ {1} ) = s _ {1} $, $ \phi _ {a _ {1} } ( s _ {2} ) = s _ {2} $, $ \phi _ {a _ {2} } ( s _ {1} ) = s _ {2} $, $ \phi _ {a _ {2} } ( s _ {2} ) = s _ {1} $. One may also consider the algebra $ \langle \widetilde{S} , \widetilde \Phi \rangle $ where $ \widetilde{S} $ is the set of words of the form $ s \alpha $, $ s \in S $, $ \alpha \in A ^ {*} $ and $ \widetilde \Phi = \{ {\widetilde \phi _ {a} } : {a \in A } \} $ is the set of unary operations on $ \widetilde{S} $ such that $ \widetilde \phi _ {a} (s a ) = s \alpha a $. The algebra $ \langle \widetilde{S} , \widetilde \Phi \rangle $ is defined by the system of $ S $- generators and the set of defining relations $ \omega = \{ {s _ {i} \alpha _ {i} = s _ {i} ^ \prime \alpha _ {i} ^ \prime } : {i = 1, 2 ,\dots } \} $. Such an algebra specifies a (usually partial) automaton $ \langle A, S, \phi \rangle $ such that if $ s _ {i} \alpha _ {i} = s _ {i} ^ \prime \alpha _ {i} ^ \prime $ is a relation from $ \omega $, the relation $ \phi ( s _ {i} , \alpha _ {i} ) = \phi ( s _ {i} ^ \prime , \alpha _ {i} ^ \prime ) $ is true. For example, the transition system $ \langle A _ {0} , S _ {0} , \phi _ {0} \rangle $ may be specified by a system of $ S _ {0} $- generators and the set of defining relations $ \omega = \{ s _ {1} = s _ {1} a _ {1} , s _ {1} = s _ {2} a _ {2} , s _ {2} = s _ {1} a _ {2} , s _ {2} = s _ {2} a _ {1} \} $. It is then assumed that $ \phi ( s _ {1} , \Lambda ) = s _ {1} $, $ \phi ( s _ {2} , \Lambda ) = s _ {2} $.

The behaviour of an automaton may be described in the language of the logic of one-place predicates. A choice of the class of formulas defining a finite automaton may be performed in various ways. The description may be incomplete, because the choice defines a class of automata whose the behaviour is identical to within the accuracy of this description. For instance, the "questionnaire" approach involves specifying classes of automata with the aid of fragments of information trees, a partial definition of the functions $ \phi $ and $ \psi $, etc.

The above ways of specifying automata may also be applied, with suitable modifications, to the behaviour of certain generalized finite automata (non-deterministic, infinite, etc.; cf. Automaton). Thus, the elements of the table $ T _ \phi $ of a finite, non-deterministic automaton may consist of arbitrary subsets of the set $ S $. The behaviour of a finite, non-deterministic acceptor is described by a regular expression, as in the case of a deterministic acceptor. Other generalizations of finite automata are finite probabilistic automata (cf. Automaton, probabilistic), automata over terms, mosaic structures, etc.

To specify a probabilistic automaton $ \langle A, S, B, \mu \rangle $ on known alphabets $ A = \{ a _ {1} \dots a _ {m} \} $, $ B = \{ b _ {1} \dots b _ {k} \} $, $ S = \{ s _ {1} \dots s _ {n} \} , $ means to specify, for any given $ i $ and $ j $( $ 1 \leq i \leq n $, $ 1 \leq j \leq m $) an arbitrary probability measure $ \mu _ {ij} (s _ {r} , b _ {q} ) $ on the set of all pairs $ (s _ {r} , b _ {q} ) $, $ r = 1 \dots n $, $ q = 1 \dots k $. To do this, one usually considers a system of square matrices with non-negative elements

$$ M ^ {q,j} = \| \mu _ {i,r} ^ {q,j} \| , $$

$$ i , r = 1 \dots n ; \ j = 1 \dots m ; \ q = 1 \dots k, $$

such that each matrix $ M ^ {j} = \sum _ {q=1} ^ {k} M ^ {q,j} $ is stochastic. The measure $ \mu $ is defined by the relation $ \mu _ {ij} ( s _ {r} , b _ {q} ) = \mu _ {i,r} ^ {q,j} $. The probabilistic automaton $ \langle A, S, B, \mu \rangle $ is considered in conjunction with a certain initial probability distribution on the set $ S $:

$$ \mu _ {0} = ( \mu _ {0} ( s _ {1} ) \dots \mu _ {0} ( s _ {n} ) ) , \ \mu _ {0} ( s _ {i} ) \geq 0 ,\ \sum _ {i=1 } ^ { n } \mu _ {0} ( s _ {i} ) = 1 . $$

Sometimes probabilistic automata are defined by specifying only the matrices $ M ^ {j} $ or only the matrices $ \overline{M}\; {} ^ {j} = \| \mu _ {i,q} ^ {j} \| $, where

$$ \mu _ {i,q} ^ {j} = \sum _ {r=1 } ^ { n } \mu _ {i,r} ^ {q,j} , $$

$ i = 1 \dots n; q = 1 \dots k; j = 1 \dots m $. Any finite Markov chain can be regarded as a finite probabilistic automaton in which the matrices $ M ^ {j} $, $ j = 1 \dots m $, are identical. The system of matrices shown below defines some probabilistic automaton $ \mathfrak A $( $ n = 2 $, $ k =2 $, $ m = 2 $) and the matrices $ M ^ {1} $, $ M ^ {2} $, $ \overline{M}\; {} ^ {1} $, $ \overline{M}\; {} ^ {2} $ of this automaton:

$$ M ^ {1,1} = \ \left \| \begin{array}{cc} \frac{1}{4} & 0 \\ \frac{1}{4} & \frac{1}{4} \\ \end{array} \right \| , \ M ^ {1,2} = \ \left \| \begin{array}{cc} \frac{1}{3} & \frac{2}{3} \\ \frac{1}{5} & \frac{1}{5} \\ \end{array} \right \| , $$

$$ M ^ {2,1} = \left \| \begin{array}{cc} \frac{1}{4} & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{4} \\ \end{array} \right \| ,\ M ^ {2,2} = \left \| \begin{array}{cc} 0 & 0 \\ \frac{2} over 5 &{%1}{5} \\ \end{array} \right \| , $$

$$ M ^ {1} = \left \| \begin{array}{cc} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \\ \end{array} \right \| , \ M ^ {2} = \left \| \begin{array}{cc} \frac{1}{3} & \frac{2}{3} \\ \frac{3}{5} & \frac{2}{5} \\ \end{array} \right \| , $$

$$ \overline{M}\; {} ^ {1} = \left \| \begin{array}{cc} \frac{1}{4} & \frac{3}{4} \\ \frac{1}{2} & \frac{1}{2} \\ \end{array} \right \| ,\ \overline{M}\; {} ^ {2} = \left \| \begin{array}{cc} 1 & 0 \\ \frac{2}{5} & \frac{3}{5} \\ \end{array} \right \| . $$

In order to define a finite automaton over terms $ \langle A, S, \sigma , \alpha _ {a} \rangle $ when the alphabets $ A = \{ a _ {1} \dots a _ {m} \} $ and $ S = \{ s _ {1} \dots s _ {n} \} $ are known one must first specify a mapping $ \sigma $ of the set $ A $ into the finite set of non-negative integers such that there exists at least one element $ a \in A $ for which $ \sigma (a) = 0 $ and, secondly, one must define, for each $ a _ {i} \in A $, $ i = 1 \dots m $, a $ \sigma (a _ {i} ) $- ary function $ \alpha _ {a _ {i} } $ mapping the set $ [S] ^ {\sigma _ {a _ {i} } } = S \times \dots \times S $ into $ S $. To each element $ a \in A $ for which $ \sigma ( a ) = 0 $ there corresponds an element $ \alpha _ {a} \in S $, called an initial state of the automaton. For example, if $ A = \{ a _ {1} , a _ {2} \} $, $ S = \{ s _ {1} , s _ {2} \} $, $ \sigma ( a _ {1} ) = 0 $, $ \sigma ( a _ {2} ) = 2 $, $ \alpha _ {a _ {1} } = s _ {1} $, $ \alpha _ {a _ {2} } ( s _ {1} , s _ {1} ) = s _ {2} $, $ \alpha _ {a _ {2} } ( s _ {1} , s _ {2} ) = s _ {1} $, $ \alpha _ {a _ {2} } ( s _ {2} , s _ {1} ) = s _ {2} $, $ \alpha _ {a _ {2} } ( s _ {2} , s _ {2} ) = s _ {2} $, then the functions $ \sigma $, $ \alpha _ {a _ {1} } $, $ \alpha _ {a _ {2} } $ define some automaton over terms $ \langle A, S, \sigma , \{ \alpha _ {a _ {1} } , \alpha _ {a _ {2} } \} \rangle $ with initial state $ s _ {1} $.

In order to specify a mosaic structure (an infinite union of transition systems of the form $ \langle A, S, \phi \rangle $, where $ A = S ^ {r} $, cf. Automaton), one must define for each integral point of the $ n $- dimensional space an ordered set of integral points; this set is called its neighbourhood. The input alphabet $ A $ of the transition system $ \langle A, S, \phi \rangle $ placed at a given point is the Cartesian product of the set of states of the transition systems placed at the points of its neighbourhood. For example, let $ S = \{ s _ {1} , s _ {2} \} $, and let the ordered set $ \{ ( \alpha - 1 , \beta ), ( \alpha , \beta + 1 ), ( \alpha + 1, \beta ) \} $ be the neighbourhood $ D _ {\alpha , \beta } $ of an integral point $ ( \alpha , \beta ) $ of the two-dimensional space. In order to specify a uniform two-dimensional mosaic structure, the function $ \phi $ is defined as follows: $ \phi ( s _ {1} , s _ {1} , s _ {1} ) = s _ {1} $; in all other cases $ \phi (s ^ \prime , s ^ {\prime\prime} , s ^ {\prime\prime\prime} ) = s _ {2} $. Here, the input alphabet $ A $ is the Cartesian product $ S \times S \times S $.

Micro-approach.

A micro-approach definition of a structural automaton describes its constituent elements and the scheme of their combination. This description may be detailed or more general. It is frequently restricted to the so-called canonical scheme of the construction of an automaton. The elements then divide into two groups: functional elements (one-state automata) and memory elements. The canonical scheme (Fig. e) consists of two functional blocks $ f $ and $ g $ to which are added Moore automata $ \mathfrak A _ {i} = \langle R _ {i} , S _ {i} , Q _ {i} , \phi _ {i} , \psi _ {i} \rangle $, $ i = 1 \dots l $, as memory elements. The blocks $ f $ and $ g $ consist of functional elements. When the structure is defined in this way, these blocks are not further described, but a specification is given (e.g. by means of tables) of the vector functions realized by these blocks:

$$ f = ( f _ {1} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} ) \dots $$

$$ \dots {}f _ {l} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} )) : $$

$$ A ^ {n} \times Q _ {1} \times \dots \times Q _ {l} \rightarrow R _ {1} \times \dots \times R _ {l} ; $$

$$ g = ( g _ {1} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} ) \dots $$

$$ \dots {}g _ {l} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} )) : $$

$$ A ^ {n} \times Q _ {1} \times \dots \times Q _ {l} \rightarrow B ^ {m} , $$

where $ A ^ {n} $ and $ B ^ {m} $ are the input and the output alphabets, respectively, of the canonical scheme.

Figure: a014060e

Figure: a014060f

This scheme specifies the structural automaton $ \langle A ^ {n} , S, B ^ {m} , \phi , \psi \rangle $, where $ S = S _ {1} \times \dots \times S _ {l} $, while the functions $ \phi $ and $ \psi $ are defined as follows:

$$ \phi ( ( s _ {1} \dots s _ {l} ) , ( a _ {1} \dots a _ {n} ) ) = \ ( s _ {1} ^ \prime \dots s _ {n} ^ \prime ) , $$

$$ s _ {i} = \phi _ {i} ( s _ {i} , f _ {i} ( a _ {1} \dots a _ {n} , \psi _ {1} ( s _ {1} ) \dots \psi _ {l} ( s _ {l} ))); $$

$$ \psi (( s _ {1} \dots s _ {l} ) , ( a _ {1} \dots a _ {n} )) = (b _ {1} \dots b _ {m} ), $$

$$ b _ {j} = g _ {j} ( a _ {1} \dots a _ {n} , \psi _ {1} ( s _ {1} ) \dots \psi _ {l} ( s _ {l} ) ) . $$

An important example of structural automata are logical networks (cf. Automaton, finite). Fig. f shows the canonical scheme of an automaton $ \langle \widetilde{A} , \widetilde{S} , \widetilde{B} , \widetilde \phi , \widetilde \psi \rangle $ isomorphic to the automaton $ \mathfrak A ^ {0} $( cf. Fig. cfor its diagram), $ \widetilde{A} = \widetilde{S} = \widetilde{B} = \{ 0, 1 \} $. The automaton $ \mathfrak A ^ \prime = \langle \widetilde{S} , \widetilde{S} , \widetilde{S} , \phi ^ \prime , \psi ^ \prime \rangle $ is a Moore automaton such that $ \phi ^ \prime (1, z) = z $, $ \phi ^ \prime (0, z)=z $.

Structural automata are frequently described by means of canonical equations, i.e. systems of the form

$$ u _ {1} ( 1 ) = s _ {0} , $$

$$ {\dots \dots \dots } $$

$$ u _ {l} ( 1 ) = s _ {0} , $$

$$ u _ {1} ( t + 1 ) = f _ {1} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) , $$

$$ {\dots \dots \dots } $$

$$ u _ {l} ( t + 1 ) = f _ {l} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) , $$

$$ y _ {1} ( t ) = g _ {1} ( u _ {1} ( t ) \dots u _ {l} ( t ), x _ {1} ( t ) \dots x _ {n} ( t ) ) , $$

$$ {\dots \dots \dots } $$

$$ y _ {m} ( t ) = g _ {m} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) , $$

where $ t = 1, 2 \dots $ is an integer parameter, $ s _ {0} \in S $, while the functions $ f _ {i} $, $ i = 1 \dots l $, $ g _ {i} $, $ i = 1 \dots m $, and the variables $ x _ {r} $, $ r = 1 \dots n $, take their values from the set $ A $. A canonical scheme in which all the memory elements are identical corresponds to this system: $ \mathfrak A _ {i} = \langle A, S, B, \phi , \psi , s _ {0} \rangle $, where $ A = S = B $, $ i = 1 \dots l $; $ \phi (a, a ^ \prime ) = a ^ \prime $, $ \psi (a, a ^ \prime ) = a $. The functioning of the automaton $ \mathfrak A _ {i} $ may essentially be described as follows. At the moment $ t $ suppose that the letter $ a(t) $ is assigned to the input of $ \mathfrak A _ {i} $, then the same letter is produced as the output of $ \mathfrak A _ {i} $ at the moment $ t + 1 $. Let Fig. f represent an automaton $ \mathfrak A $ whose canonical equations have the form

$$ u ( 1 ) = 0 , $$

$$ u ( t + 1 ) = x ( t ) + u ( t ) ( \mathop{\rm mod} 2 ), $$

$$ y( t ) = x ( t ) \lor u ( t ) . $$

In the general case, a description of structural automata involves defining a selection of elementary automata and a certain class of "correctly constructed" schemes (networks), the latter usually being defined by induction.

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)

Comments

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