View source for Automata, experiments with

A method of obtaining information about the internal structure of an automaton from its behaviour as can be deduced from external experiments (that is, experiments where input words are fed into an automaton, the corresponding sequence of output words is examined and conclusions are drawn on the basis of these observations).

Experiments with automata can be used to seek approaches to the solution of the following problems:

1) Given that an automaton is in an initial state it is required to determine this state.

2) The construction of an experiment that transfers an automaton from any state to some pre-assigned state (the adjustment problem).

3) The verification of the correct functioning of an automaton. It is required to find out by means of an experiment if a given automaton functions correctly.

4) The diagnostic of an automaton. It is required to find out not only if an automaton is in good working order, but also what kind of malfunction occurs.

5) The problem of identifying an automaton from a given class (deciphering). Knowing that the automaton, viewed as a  "black box" , belongs to a given set, it is required to find out which element the automaton is.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140401.png" /> be a class of initialized automata with input alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140402.png" /> and output alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140403.png" />. Next, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140404.png" /> be the collection of all words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140405.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140406.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140407.png" />. An experiment with the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140408.png" /> is a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a0140409.png" /> of all pairs of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404010.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404012.png" /> is a word into which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404013.png" /> produces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404014.png" />.

==The classification of experiments.==
The following types of experiments are usually considered:

1) A simple unconditional experiment — a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404016.png" /> consists of a single word. In the process of experimenting the single element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404017.png" /> is fed into the input of the automaton and the resulting output is some word from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404018.png" />.

2) A simple conditional experiment — a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404019.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404020.png" /> consists of a single word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404021.png" /> and where for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404022.png" /> the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404023.png" /> depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404025.png" />. Thus, in the process of experimenting with automata every subsequent letter of the input word depends on the output word obtained earlier.

3) A multiple unconditional experiment — a generalization of a simple unconditional experiment to the case when the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404026.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404027.png" /> consists of more than one word. It is usually assumed that in the process of execution of the given experiment there is more than one specimen of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404028.png" />, or that the automaton can be reset in its initial state.

4) A multiple conditional experiment — a generalization of a simple conditional experiment to the case when the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404029.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404030.png" /> consists of more than one word:

<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/a014040/a01404031.png" /></td> </tr></table>

Moreover, two possibilities can be distinguished here: a) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404033.png" /> the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404034.png" /> depends only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404035.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404036.png" /> consists of the single word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404037.png" />; or b) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404039.png" /> the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404040.png" /> depends on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404041.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404042.png" /> is the set consisting of the collections <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404043.png" /> and the index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404044.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404045.png" /> coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404046.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404047.png" /> or with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404048.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404049.png" />.

==Measures of the complexity of experiments.==
These are some numerical characteristics that estimate the degree of complexity of an experiment. For a multiple experiment the usual measures of complexity are the height of the experiment — the number of symbols of the largest input word, the multiplicity — the number of input words, and the length — the total number of symbols in all the input words. It is considered that the measure of complexity of a simple experiment is its length (the number of symbols of the input word used).

===Some results.===
A Moore automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404050.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404051.png" /> states, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404052.png" /> input and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404053.png" /> output symbols is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404054.png" />-automaton. The following theorem on the distinguishability of states by a simple experiment holds: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404055.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404056.png" />-automaton with all states distinct, then the distinguishability of any two states can be established by means of a simple experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404057.png" />, and the bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404058.png" /> cannot be lowered (see [[#References|[4]]]).

The problem of determining the initial state of an automaton can be solved by means of a simple unconditional experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404059.png" />, 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/a014040/a01404060.png" /></td> </tr></table>

Adjustment for an automaton with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404061.png" /> states of which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404062.png" /> are admissible can always be solved by means of a simple unconditional experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404063.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404064.png" />, and this bound cannot be improved.

As a rule, the above estimates are exact only for a small number of automata. It has been established (see [[#References|[4]]]) that the problem of determining the initial state for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404065.png" />-automata with two admissible states can be solved by means of a simple unconditional experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404066.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404067.png" />, and the adjustment problem for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404068.png" />-automata by means of a simple unconditional experiment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404069.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014040/a01404070.png" />.

There is no algorithm that would permit the decyphering of initialized Mealy automata with unknown number of states. However, it turns out that a great part of such automata can nevertheless be decyphered.

Experiments with automata are also used as tools for the control of the functioning of automata. A unified approach has been developed to problems of control of automata, which makes it possible to indicate fundamental methods for their solution. An effective algorithm has been constructed for finding all dead-end multiple experiments for various automata (see [[#References|[2]]]).

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  E.F. Moore,   "Gedanken-experiments on sequential machines"  C.E. Shannon (ed.)  J. McCarthy (ed.) , ''Automata studies'' , Princeton Univ. Press  (1956)  pp. 179–210</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  S.V. Yablonskii,   "Mathematical logic, theory of algorithms and theory of sets"  ''Trudy Mat. Inst. Steklov.'' , '''133'''  pp. 263–272  (In Russian)</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  B.A. Trakhtenbrot,   Ya.M. Bardzdin',   "Finite automata. Behaviour and synthesis" , North-Holland  (1973)</TD></TR>
<TR><TD valign="top">[4]</TD> <TD valign="top">  T.N. Hibbard,   "Lower upper bounds on minimal terminal state experiments for two classes of sequential machines"  ''J. Assoc. Comput. Mach.'' , '''8''' :  4  (1961)  pp. 601–612</TD></TR>
</table>

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  John H. Conway, ''Regular Algebra and Finite Machines'', Chapman & Hall (1971)</TD></TR>
</table>