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

2: Equivalent Automata

Lecture



Abstract: The concepts of the reaction of an automaton and equivalent automata are given. The methods of mutual transformation into equivalent automata are given.
Keywords: Automaton reaction, automaton, reaction, output word, input word, Moore automaton, Mile automaton, graph, equivalence, equivalent automata, table, intersection, interpretation, arc, function, set of states

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

  2: Equivalent 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   2: Equivalent Automata in state   2: Equivalent Automata as in the Miles automaton, and after the automaton passed into the state   2: Equivalent Automata .

2.2 Equivalent Automata

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

  2: Equivalent Automata

Fig. 2.2.
  2: Equivalent Automata

Fig. 2.3.

The input is the same input word:   2: Equivalent Automata . As a result, the output word is formed.   2: Equivalent 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   2: Equivalent Automata and   2: Equivalent 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 exit table of the Miles machine is obtained from the transition table by replacing the symbol   2: Equivalent Automata standing at the line crossing   2: Equivalent Automata and column   2: Equivalent Automata per character   2: Equivalent Automata marking the column   2: Equivalent 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 automaton table representing the automaton transitions, and the output table 2.6 is obtained as follows. It is believed that on the transition from the state   2: Equivalent Automata in state   2: Equivalent Automata in the equivalent Miles machine, the same output signal should be generated as in the Moore machine, after the state machine went into   2: Equivalent Automata i.e. output signal   2: Equivalent 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   2: Equivalent Automata in state   2: Equivalent Automata . In Moore's machine as   2: Equivalent Automata matches the output signal   2: Equivalent Automata , therefore in table.2.6 at the transition from the state   2: Equivalent Automata on input signal   2: Equivalent Automata set   2: Equivalent 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   2: Equivalent Automata being molded into   2: Equivalent Automata , is transferred to all the arcs entering this vertex, a graphical interpretation of this is shown in Figure 2.4, and an example of the transformation of the Moore machine gun into the equivalent Mealy machine is shown in Fig. 2.5.

  2: Equivalent Automata

Fig. 2.4.
  2: Equivalent 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.

  2: Equivalent Automata

Fig. 2.6.

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

  2: Equivalent Automata

Fig. 2.7.

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

  2: Equivalent Automata ;

  2: Equivalent Automata ;

  2: Equivalent Automata ;

  2: Equivalent Automata .

Redesigning   2: Equivalent Automata accordingly as   2: Equivalent Automata , we get the graph shown in Figure 2.8-2.9.

  2: Equivalent Automata

Fig. 2.8.
  2: Equivalent 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