You get a bonus - 1 coin for daily activity. Now you have 1 coin

Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.

Lecture



2.1. Reaction machine

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.   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . The automaton is in the initial state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . Incoming input signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. puts the machine in state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and the output signal is formed on this transition at the same discrete moment of time.   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . In the second moment of time   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. an input signal acts on the machine   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. which puts the machine in state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , and on this transition at the same discrete point in time   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. output signal is generated   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and so on. As a result, the input word   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. formed output word   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. which is the reaction of the machine.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.1.

Table 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   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. in state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. as in the Miles automaton, and after the automaton passed into the state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. .

2.2 Equivalent Automata

Automatic Miles   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. Fig.2.2 is set to its original state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. .An input is the input word:   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . As a result, the output word is formed.   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. which is the reaction of the automaton (Table 2.2). Moore's gun   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. the graph, which is presented in Fig.2.3, is set to its original state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. .

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.2.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.3.

The input is the same input word:   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . As a result, the output word is formed.   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. which is the reaction of the automaton (Table 2.3).

Table 2.2.
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
Table 2.3.
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   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. are called equivalent if:

  • input and output alphabets are the same;
  • their reactions from the initial state to any input word are the same;

There is a theorem: for any Moore machine gun, there is an equivalent Mealy machine gun and vice versa.

2.3 Conversion of Moore’s Automata to Mile Equivalent Automata

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   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. standing at the line crossing   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and column   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. per character   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. marking the column   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. 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   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. in state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. in the equivalent Miles machine, the same output signal should be generated as in the Moore machine, after the state machine went into   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. i.e. output signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. .

Table 2.4.
w1 w2 w3 w2 w3
a1 a2 a3 a4 a5
z1 a2 a5 a5 a3 a3
z2 a4 a2 a2 a1 a1
Table 2.5.
a1 a2 a3 a4 a5
z1 a2 a5 a5 a3 a3
z2 a4 a2 a2 a1 a1
Table 2.6.
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   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. in state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . In Moore's machine as   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. matches the output signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , therefore in table.2.6 at the transition from the state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. on input signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. set   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and so on.

In the graphic task of Moore’s automaton, the transition to the Mile’s automaton is performed as follows: output signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. being molded into   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , 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.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.4.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.5.

2.4 Converting Miles Automata to Moore Equivalent Automata

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.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.6.

In Moore's automaton, the output signal   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. formed as a function   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , and in the Miles machine -   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . And   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. - the current state of the machine,   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. - the previous state of the machine. Thus, the state   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. corresponds to a group   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. whose number is equal to the number of different output signals   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. located on incoming arcs. A graphic interpretation of this is shown in Figure 2.7.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.7.

Let the Mile machine gun be given:   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . I want to go to the equivalent Moore machine   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , that is, you need to build such an Moore automaton:   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , what   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. and   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . Consider an example. Dan machine Miles Fig.2.8-2.9. We construct the set of states of the automaton.   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. . For this we find the pair:

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. ;

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. ;

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. ;

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. .

Redesigning   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. accordingly as   Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata. , we get the graph shown in Figure 2.8-2.9.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.8.

  Equivalent Automata. Converting Moore Automata to Equivalent Mile Automata.


Fig. 2.8.

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Theory of Automata

Terms: Theory of Automata