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 . 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 translates the machine to the state 2: Equivalent Automata , 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 automaton.

Fig. 2.1.

Table 2.1.
Time t	t1	t2	t3	t4	t5
Input signals	z ₁	z ₂	z ₁	z ₂	z ₂
States	a ₁	a ₂	a ₃	a ₃	a ₂	a ₁
Output signals	w ₃	w ₁	w ₁	w ₂	w ₂

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

2.2 Equivalent Automata

Automatic Miles 2: Equivalent Automata 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: 2: Equivalent Automata . As a result, the output word is formed. 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
Output word	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
Output word	automatic reaction

Two automatic 2: Equivalent Automata and 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 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 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 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 .

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 . 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 2: Equivalent Automata being molded into , 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.

Fig. 2.4.

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.

Fig. 2.6.

In Moore's automaton, the output signal 2: Equivalent Automata 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: 2: Equivalent Automata . 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: