Namespaces
Variants
Actions

Difference between revisions of "Automata, methods of specification of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(cf Automata, composition of)
m (OldImage template added)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
a0140601.png
 +
$#A+1 = 329 n = 0
 +
$#C+1 = 329 : ~/encyclopedia/old_files/data/A014/A.0104060 Automata, methods of specification of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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|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.
 
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|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.==
 
==Macro-approach.==
To specify a finite automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140601.png" /> for given alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140602.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140603.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140604.png" /> is tantamount to describing the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140605.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140606.png" /> or to describing the behaviour of this automaton (cf. [[Automaton, behaviour of an|Automaton, behaviour of an]]). The functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140607.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140608.png" /> are often defined by means of a table, a diagram or a matrix of transitions. The table of transitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a0140609.png" /> of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406010.png" /> consists of two subtables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406014.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406016.png" />. The functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406018.png" /> are defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406020.png" />. If all the columns of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406021.png" /> coincide, the table <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406022.png" /> defines a Moore automaton. For instance, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406025.png" />; the table <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406026.png" /> (Fig. a) will then specify the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406028.png" /> of some automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406029.png" /> (Fig. bshows the subtables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406032.png" />).
+
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|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 $).
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060a.gif" />
Line 12: Line 55:
 
Figure: a014060b
 
Figure: a014060b
  
The diagram of (transitions of) an automaton is an oriented graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406033.png" /> with a one-to-one correspondence between the vertices of the graph and the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406034.png" />, and between the edges of the graph and certain sets of pairs of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406037.png" />. Each vertex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406038.png" /> is the starting point of at least one edge, and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406039.png" /> of all pairs assigned to the edges with the same vertex as their origin has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406040.png" />. The functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406042.png" /> are then defined as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406044.png" /> if the pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406045.png" /> is assigned to the edge issuing from from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406046.png" /> and if this edge ends in the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406047.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406048.png" />.
+
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} $.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060c.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060c.gif" />
Line 18: Line 76:
 
Figure: a014060c
 
Figure: a014060c
  
The transition matrix is used to describe the functioning of the transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406049.png" /> (cf.[[Automaton, finite|Automaton, finite]]). It is represented by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406050.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406051.png" /> whose elements are subsets of the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406052.png" /> (including the empty subset) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406053.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406054.png" />, so that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406055.png" /> the relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406056.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406057.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406058.png" /> are true. In order to extend the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406059.png" /> to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406060.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406061.png" /> is the set of all words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406062.png" /> including the empty word), one considers the sequence of powers of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406063.png" />. Multiplication of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406064.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406065.png" /> is a word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406067.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406068.png" /> is an element of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406069.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406070.png" />. Thus, the transition matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406071.png" /> of the transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406072.png" /> and the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406073.png" /> have, respectively, the forms:
+
The transition matrix is used to describe the functioning of the transition system $  \langle  A, S, \phi \rangle $(
 +
cf.[[Automaton, finite|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 \|
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406074.png" /></td> </tr></table>
+
\begin{array}{cc}
 +
a _ {1}  &a _ {2}  \\
 +
a _ {2}  &a _ {1}  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406075.png" /></td> </tr></table>
+
\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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406076.png" /> (transformer), one must define the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406077.png" /> which maps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406078.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406079.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406080.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406081.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406082.png" /> are the sets of all the superwords over the alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406084.png" />, respectively).
+
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).
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060d.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060d.gif" />
Line 32: Line 143:
 
Figure: a014060d
 
Figure: a014060d
  
This function may be defined by means of an information tree. From each vertex of the information tree there issue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406085.png" /> edges, which are in one-to-one correspondence with the respective letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406086.png" />. To each vertex is assigned a state of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406087.png" />, while to each edge is assigned a letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406088.png" /> in the following way. The state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406089.png" /> is assigned to the root. If the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406090.png" /> has been assigned to some vertex, the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406091.png" /> is assigned to the edge corresponding to the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406092.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406093.png" />, while to the vertex in which this edge terminates the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406094.png" /> is assigned. To each word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406095.png" /> corresponds a unique sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406096.png" /> of edges of this tree such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406097.png" /> issues from the root and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406098.png" /> issues from the vertex of termination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a01406099.png" />. The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060100.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060101.png" /> is the letter from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060102.png" /> assigned to the edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060104.png" />, is identical with the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060105.png" />. If the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060106.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060107.png" /> (the left-hand edges, issuing from the vertices, correspond to the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060108.png" />, while the right-hand edges correspond to the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060109.png" />).
+
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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060110.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060111.png" /> are finite alphabets, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060112.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060113.png" /> is an [[Axiom scheme|axiom scheme]] of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060114.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060115.png" /> is the set of schemes of derivation rules of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060117.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060118.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060119.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060120.png" /> is a variable which assumes values from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060121.png" />. If, moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060122.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060123.png" /> belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060124.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060125.png" />. The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060126.png" /> is deducible in the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060127.png" /> if there exists a sequence of words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060128.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060129.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060130.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060131.png" />, by the application of a certain rule from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060132.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060133.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060134.png" /> does not contain the rule <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060135.png" />. A grammar generating a regular event has a similar form. It is given by the quadruple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060136.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060137.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060138.png" /> is an axiom, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060139.png" /> is the set of rules of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060140.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060141.png" />. The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060142.png" /> is deducible in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060143.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060144.png" /> includes the rules <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060145.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060146.png" />. Algorithms which yield the transition matrix of an automaton from formal schemes of this type are known. Thus, an event represented in the acceptor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060147.png" /> by the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060148.png" /> may be defined, for example, as the set of words that are deducible in the semi-Thue system
+
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|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|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060149.png" /></td> </tr></table>
+
$$
 +
{\mathcal T}  = \langle  A _ {0} , S _ {0} , \xi = \{ s _ {1} X \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060150.png" /></td> </tr></table>
+
$$
 +
\omega = \{ s _ {1} a _ {2} X \rightarrow s _ {2} X ; s _ {1} a _ {1} X \rightarrow s _ {1} X ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060151.png" /></td> </tr></table>
+
$$
 +
{}{}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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060152.png" /> may be specified as an algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060153.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060154.png" /> is the set of unary operations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060155.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060156.png" />. Thus, the transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060157.png" /> may be regarded as the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060158.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060159.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060160.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060161.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060162.png" />. One may also consider the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060163.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060164.png" /> is the set of words of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060165.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060166.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060167.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060168.png" /> is the set of unary operations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060169.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060170.png" />. The algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060171.png" /> is defined by the system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060172.png" />-generators and the set of defining relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060173.png" />. Such an algebra specifies a (usually partial) automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060174.png" /> such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060175.png" /> is a relation from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060176.png" />, the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060177.png" /> is true. For example, the transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060178.png" /> may be specified by a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060179.png" />-generators and the set of defining relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060180.png" />. It is then assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060181.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060182.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060183.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060184.png" />, etc.
+
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|Automaton]]). Thus, the elements of the table <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060185.png" /> of a finite, non-deterministic automaton may consist of arbitrary subsets of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060186.png" />. 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|Automaton, probabilistic]]), automata over terms, mosaic structures, 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|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|Automaton, probabilistic]]), automata over terms, mosaic structures, etc.
  
To specify a probabilistic automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060187.png" /> on known alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060188.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060189.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060190.png" /> means to specify, for any given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060191.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060192.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060193.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060194.png" />) an arbitrary probability measure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060195.png" /> on the set of all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060196.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060197.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060198.png" />. To do this, one usually considers a system of square matrices with non-negative elements
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060199.png" /></td> </tr></table>
+
$$
 +
M  ^ {q,j}  = \| \mu _ {i,r}  ^ {q,j} \| ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060200.png" /></td> </tr></table>
+
$$
 +
i , r  = 1 \dots n ; \  j  = 1 \dots m ; \  q  = 1 \dots k,
 +
$$
  
such that each matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060201.png" /> is stochastic. The measure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060202.png" /> is defined by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060203.png" />. The probabilistic automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060204.png" /> is considered in conjunction with a certain initial probability distribution on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060205.png" />:
+
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 $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060206.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060207.png" /> or only the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060208.png" />, where
+
Sometimes probabilistic automata are defined by specifying only the matrices $  M  ^ {j} $
 +
or only the matrices $  \overline{M}\; {}  ^ {j} = \| \mu _ {i,q}  ^ {j} \| $,  
 +
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060209.png" /></td> </tr></table>
+
$$
 +
\mu _ {i,q}  ^ {j}  = \sum _ {r=1 } ^ { n }  \mu _ {i,r}  ^ {q,j} ,
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060210.png" />. Any finite [[Markov chain|Markov chain]] can be regarded as a finite probabilistic automaton in which the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060211.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060212.png" />, are identical. The system of matrices shown below defines some probabilistic automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060213.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060214.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060215.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060216.png" />) and the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060217.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060218.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060219.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060220.png" /> of this automaton:
+
$  i = 1 \dots n;  q = 1 \dots k;  j = 1 \dots m $.  
 +
Any finite [[Markov chain|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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060221.png" /></td> </tr></table>
+
$$
 +
M  ^ {1,1}  = \
 +
\left \|
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060222.png" /></td> </tr></table>
+
\begin{array}{cc}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060223.png" /></td> </tr></table>
+
\frac{1}{4}
 +
  & 0 \\
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060224.png" /></td> </tr></table>
+
\frac{1}{4}
 +
  &
 +
\frac{1}{4}
 +
  \\
 +
\end{array}
  
In order to define a finite automaton over terms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060225.png" /> when the alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060226.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060227.png" /> are known one must first specify a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060228.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060229.png" /> into the finite set of non-negative integers such that there exists at least one element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060230.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060231.png" /> and, secondly, one must define, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060232.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060233.png" />, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060234.png" />-ary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060235.png" /> mapping the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060236.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060237.png" />. To each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060238.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060239.png" /> there corresponds an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060240.png" />, called an initial state of the automaton. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060241.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060242.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060243.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060244.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060245.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060246.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060247.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060248.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060249.png" />, then the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060250.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060251.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060252.png" /> define some automaton over terms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060253.png" /> with initial state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060254.png" />.
+
\right \| ,
 +
\  M  ^ {1,2}  = \
 +
\left \|
  
In order to specify a mosaic structure (an infinite union of transition systems of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060255.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060256.png" />, cf. [[Automaton|Automaton]]), one must define for each integral point of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060257.png" />-dimensional space an ordered set of integral points; this set is called its neighbourhood. The input alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060258.png" /> of the transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060259.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060260.png" />, and let the ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060261.png" /> be the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060262.png" /> of an integral point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060263.png" /> of the two-dimensional space. In order to specify a uniform two-dimensional mosaic structure, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060264.png" /> is defined as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060265.png" />; in all other cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060266.png" />. Here, the input alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060267.png" /> is the Cartesian product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060268.png" />.
+
\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}{5}
 +
&
 +
\frac{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|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.==
 
==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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060269.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060270.png" /> to which are added Moore automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060271.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060272.png" />, as memory elements. The blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060273.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060274.png" /> 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:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060275.png" /></td> </tr></table>
+
$$
 +
= ( f _ {1} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} ) \dots
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060276.png" /></td> </tr></table>
+
$$
 +
\dots
 +
{}f _ {l} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} )) :
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060277.png" /></td> </tr></table>
+
$$
 +
A  ^ {n} \times Q _ {1} \times \dots \times Q _ {l}  \rightarrow  R _ {1} \times \dots \times R _ {l} ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060278.png" /></td> </tr></table>
+
$$
 +
= ( g _ {1} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} ) \dots
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060279.png" /></td> </tr></table>
+
$$
 +
\dots
 +
{}g _ {l} ( x _ {1} \dots x _ {n} , u _ {1} \dots u _ {l} )) :
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060280.png" /></td> </tr></table>
+
$$
 +
A  ^ {n} \times Q _ {1} \times \dots \times Q _ {l}  \rightarrow  B  ^ {m} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060281.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060282.png" /> are the input and the output alphabets, respectively, of the canonical scheme.
+
where $  A  ^ {n} $
 +
and $  B  ^ {m} $
 +
are the input and the output alphabets, respectively, of the canonical scheme.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060e.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/a014060e.gif" />
Line 101: Line 529:
 
Figure: a014060f
 
Figure: a014060f
  
This scheme specifies the structural automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060283.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060284.png" />, while the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060285.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060286.png" /> are defined as follows:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060287.png" /></td> </tr></table>
+
$$
 +
\phi ( ( s _ {1} \dots s _ {l} ) , ( a _ {1} \dots a _ {n} ) )  = \
 +
( s _ {1}  ^  \prime  \dots s _ {n}  ^  \prime  ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060288.png" /></td> </tr></table>
+
$$
 +
s _ {i}  = \phi _ {i} ( s _ {i} , f _ {i} ( a _ {1} \dots a _ {n} , \psi _ {1} ( s _ {1} ) \dots \psi _ {l} ( s _ {l} )));
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060289.png" /></td> </tr></table>
+
$$
 +
\psi (( s _ {1} \dots s _ {l} ) , ( a _ {1} \dots a _ {n} ))  = (b _ {1} \dots b _ {m} ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060290.png" /></td> </tr></table>
+
$$
 +
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|Automaton, finite]]). Fig. f shows the canonical scheme of an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060291.png" /> isomorphic to the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060292.png" /> (cf. Fig. cfor its diagram), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060293.png" />. The automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060294.png" /> is a Moore automaton such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060295.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060296.png" />.
+
An important example of structural automata are logical networks (cf. [[Automaton, finite|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
 
Structural automata are frequently described by means of canonical equations, i.e. systems of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060297.png" /></td> </tr></table>
+
$$
 +
u _ {1} ( 1 )  = s _ {0} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060298.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots }
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060299.png" /></td> </tr></table>
+
$$
 +
u _ {l} ( 1 )  = s _ {0} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060300.png" /></td> </tr></table>
+
$$
 +
u _ {1} ( t + 1 )  = f _ {1} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060301.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots }
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060302.png" /></td> </tr></table>
+
$$
 +
u _ {l} ( t + 1 )  = f _ {l} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060303.png" /></td> </tr></table>
+
$$
 +
y _ {1} ( t )  = g _ {1} ( u _ {1} ( t ) \dots u _ {l} ( t ), x _ {1} ( t ) \dots x _ {n} ( t ) ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060304.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots }
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060305.png" /></td> </tr></table>
+
$$
 +
y _ {m} ( t )  = g _ {m} ( u _ {1} ( t ) \dots u _ {l} ( t ) , x _ {1} ( t ) \dots x _ {n} ( t ) ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060306.png" /> is an integer parameter, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060307.png" />, while the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060308.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060309.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060310.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060311.png" />, and the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060312.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060313.png" />, take their values from the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060314.png" />. A canonical scheme in which all the memory elements are identical corresponds to this system: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060315.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060316.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060317.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060318.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060319.png" />. The functioning of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060320.png" /> may essentially be described as follows. At the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060321.png" /> suppose that the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060322.png" /> is assigned to the input of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060323.png" />, then the same letter is produced as the output of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060324.png" /> at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060325.png" />. Let Fig. f represent an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060326.png" /> whose canonical equations have the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060327.png" /></td> </tr></table>
+
$$
 +
u ( 1 )  = 0 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060328.png" /></td> </tr></table>
+
$$
 +
u ( t + 1 )  = x ( t ) + u ( t )  (  \mathop{\rm mod}  2 ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014060/a014060329.png" /></td> </tr></table>
+
$$
 +
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.
 
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.
Line 145: Line 636:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C.E. Shannon (ed.)  J. McCarthy (ed.) , ''Automata studies'' , Princeton Univ. Press  (1956)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.M. Glushkov,  "Synthesis of numerical automata" , Moscow  (1962)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C.E. Shannon (ed.)  J. McCarthy (ed.) , ''Automata studies'' , Princeton Univ. Press  (1956)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.M. Glushkov,  "Synthesis of numerical automata" , Moscow  (1962)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].
 
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].
 +
 +
{{OldImage}}

Latest revision as of 07:31, 26 March 2023


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}{5} & \frac{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.


🛠️ This page contains images that should be replaced by better images in the SVG file format. 🛠️
How to Cite This Entry:
Automata, methods of specification of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_methods_of_specification_of&oldid=34728
This article was adapted from an original article by V.A. BuevichS.V. Aleshin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article