Lecture
The reaction of an automaton is the sequence of output signals of an automaton obtained under the influence of a certain sequence of input signals, that is, the reaction is the output word of the automaton to a specific input word.
So for an automaton in Figure 2.1, the formation of the reaction is presented in Table 2.1. The input of the machine is a sequence of input signals. 
. The automaton is in the initial state 
. Incoming input signal 
puts the machine in state 
and the output signal is formed on this transition at the same discrete moment of time. 
. In the second moment of time 
an input signal acts on the machine 
which puts the machine in state 
, and on this transition at the same discrete point in time output signal is generated 
and so on. As a result, the input word 
formed output word 
which is the reaction of the machine.
Fig. 2.1.
| Time t | t1 | t2 | t3 | t4 | t5 | |
|---|---|---|---|---|---|---|
| Input signals | z 1 | z 2 | z 1 | z 2 | z 2 | |
| States | a 1 | a 2 | a 3 | a 3 | a 2 | a 1 |
| Output signals | w 3 | w 1 | w 1 | w 2 | w 2 |
For Moore's automaton, the formation of a reaction occurs in a similar way, with the only difference that in Moore’s automaton, the output signal is not given at the transition of the automaton from the state 
in state 
as in the Miles automaton, and after the automaton passed into the state .
Automatic Miles 
Fig.2.2 is set to its original state 
.An input is the input word: 
. As a result, the output word is formed. 
which is the reaction of the automaton (Table 2.2). Moore's gun 
the graph, which is presented in Fig.2.3, is set to its original state .
Fig. 2.2.
Fig. 2.3.
The input is the same input word: 
. As a result, the output word is formed. 
which is the reaction of the automaton (Table 2.3).
| Moments of time | t1 | t2 | t3 | t4 | t5 | t6 | t7 |
|---|---|---|---|---|---|---|---|
| Input word | z1 | z1 | z2 | z1 | z2 | z2 | |
| States | a1 | a2 | a1 | a1 | a2 | a3 | a2 |
| Output word | w1 | w2 | w1 | w1 | w1 | w2 | |
| automatic reaction | |||||||
| Moments of time | t1 | t2 | t3 | t4 | t5 | t6 | t7 |
|---|---|---|---|---|---|---|---|
| Input word | z1 | z1 | z2 | z1 | z2 | z2 | |
| States | a1 | a4 | a2 | a1 | a4 | a3 | a5 |
| Output word | w1 | w1 | w2 | w1 | w1 | w1 | w2 |
| automatic reaction | |||||||
Two automatic and are called equivalent if:
There is a theorem: for any Moore machine gun, there is an equivalent Mealy machine gun and vice versa.
In the tabular task, the transition table of the Mile automaton coincides with the transition table of the Moore automaton. The output table of the Millip automatic machine is obtained from the transition table by replacing the symbol standing at the line crossing 
and column per character 
marking the column in the combined table of Moore’s machine gun.
Let Moore's automaton be given (Table 2.4). The transition table of the equivalent Mile automaton (Table 2.5) coincides with the combined Moore machine table, which represents the transitions of the automaton, and the output table 2.6 is obtained as follows. It is believed that on the transition from the state in state in the equivalent Miles machine, the same output signal should be generated as in the Moore machine, after the state machine went into 
i.e. output signal .
| w1 | w2 | w3 | w2 | w3 | |
|---|---|---|---|---|---|
| a1 | a2 | a3 | a4 | a5 | |
| z1 | a2 | a5 | a5 | a3 | a3 |
| z2 | a4 | a2 | a2 | a1 | a1 |
| a1 | a2 | a3 | a4 | a5 | |
|---|---|---|---|---|---|
| z1 | a2 | a5 | a5 | a3 | a3 |
| z2 | a4 | a2 | a2 | a1 | a1 |
| a1 | a2 | a3 | a4 | a5 | |
|---|---|---|---|---|---|
| z1 | w2 | w3 | w3 | w3 | w3 |
| z2 | w2 | w2 | w2 | w1 | w1 |
Consider the transition of the automaton from the state 
in state 
. In Moore's machine as matches the output signal 
, therefore in table.2.6 at the transition from the state on input signal 
set and so on.
In the graphic task of Moore’s automaton, the transition to the Mile’s automaton is performed as follows: output signal being molded into , is transferred to all arcs included in this vertex, a graphical interpretation of this is shown in Fig. 2.4, and an example of the transformation of the Moore machine gun into the equivalent Mealy machine is shown in Fig. 2.5.
Fig. 2.4.
Fig. 2.5.
Restriction: In the Mile machine there should be no transition states, i.e. States in which there is at least one outgoing arc and there is not a single incoming arc, as shown in Fig. 2.6.
Fig. 2.6.
In Moore's automaton, the output signal 
formed as a function 
, and in the Miles machine - 
. And - the current state of the machine, - the previous state of the machine. Thus, the state corresponds to a group 
whose number is equal to the number of different output signals 
located on incoming arcs. A graphic interpretation of this is shown in Figure 2.7.
Fig. 2.7.
Let the Mile machine gun be given: 
. I want to go to the equivalent Moore machine 
, that is, you need to build such an Moore automaton: 
, what 
and 
. Consider an example. Dan machine Miles Fig.2.8-2.9. We construct the set of states of the automaton. 
. For this we find the pair:
;
;
;
.
Redesigning 
accordingly as 
, we get the graph shown in Figure 2.8-2.9.
|
Fig. 2.8. |
Fig. 2.8. |
Comments
To leave a comment
Theory of Automata
Terms: Theory of Automata