Moore Machine

Moore Machine Example

Moore automaton ( abstract automaton of the second kind ) in the theory of calculations is a finite automaton in which the output value of the signal depends only on the current state of the given automaton and does not depend directly, in contrast to the Mealy automaton , on the input values. Moore's assault rifle is named after Edward F. Moore , who described its properties, who published his research in 1956 in the Gedanken-experiments on Sequential Machines ^[1] .

Content

Formal Definition

Moore's automaton can be defined as a tuple of 6 elements, including:

the set of internal states S (internal alphabet);
initial state s ₀ ;
set of input signals X (input alphabet);
set of output signals Y (output alphabet);
transition function $\Phi :S\times X\rightarrow S$ ${\ displaystyle \ Phi: S \ times X \ rightarrow S}$ .
output function $\operatorname {G} :S\rightarrow Y$ ${\ displaystyle \ operatorname {G}: S \ rightarrow Y}$ .

Miles Link

For any Moore automaton, there exists an equivalent Mealy automaton : any Moore automaton can be transformed into a Mealy automaton by adding a number of internal states. The converse, strictly speaking, is not true: the fact is that the signal at the output of the Moore automaton depends only on the input signal at previous instants of time, and the output signal for the Mealy automaton can depend on the input signal at the current moment of time. In the general case, only a Moore automaton, which is almost equivalent to it, can be constructed for a Mili automaton: namely, its output will be shifted in time by 1 ^[2] . If we change the definition of a Moore automaton in such a way that the automaton will output a value $\operatorname {G} (s)$ ${\ displaystyle \ operatorname {G} (s)}$ at the end of the transaction $s\rightarrow s'$ ${\ displaystyle s \ rightarrow s'}$ , and not at the beginning, then such automata will be completely equivalent to Miles.

Job Methods

A diagram is a directed graph depicted on a plane, the vertices of which correspond one-to-one to the states of the automaton, and the arcs to the input symbols.
A transition-output table , in the cells of which for each pair of values of the arguments x (t) , s (t) the future internal states s (t + 1) are put down. The values of the output signals y (t) are presented in a separate column.

Jump Table

	y ₁	y ₂	y ₃	y ₁	y ₂	y ₂	y ₃
	s ₁	s ₂	s ₃	s ₄	s ₅	s ₆	s ₇
$x_{1}$ ${\ displaystyle x_ {1}}$	s ₅	s ₄	s ₅	s ₃	s ₄	s ₂	s ₅
$x_{2}$ ${\ displaystyle x_ {2}}$	s ₇	s ₁	s ₄	s ₂	s ₁	s ₃	s ₄

Notes

↑ Moore, Edward F. Gedanken-experiments on Sequential Machines (Neopr.) // Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - No. 34 . - S. 129-153 .
↑ Edward A. Lee and Sanjit A. Seshia. Introduction to Embedded Systems . - Second Edition. - MIT Press, 2017 .-- P. 58. - ISBN 978-0-262-53381-2 .

Literature

Karacuba AA Experimente mit Automaten (German) // Elektron. Inform.-verarb. Kybernetik, 11, 611-612 (1975). (German)
Karatsuba A. A. Solution of a problem from the theory of finite automata // Uspekhi Mat. Nauk, v. 15, No. 3 (93), p. 157-159 (1960). (Russian)
Karatsuba A. A. List of scientific papers (Russian)
Karacuba AA Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611-612 (1975). (eng.)
Moore EF Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956). (eng.)

[gedanken-1] Moore, Edward F. Gedanken-experiments on Sequential Machines (Neopr.) // Automata Studies, Annals of Mathematical Studies. - Princeton, NJ: Princeton University Press, 1956. - No. 34 . - S. 129-153 .

[2] Edward A. Lee and Sanjit A. Seshia. Introduction to Embedded Systems . - Second Edition. - MIT Press, 2017 .-- P. 58. - ISBN 978-0-262-53381-2 .