Moore machine

A Moore automaton is a finite automaton whose output, in contrast to a Mealy automaton, depends exclusively on its state. When a state is reached, an output is generated which is independent of the transition to this state. Moore automata are named after the mathematician Edward F. Moore (1925–2003). They can be deterministic or nondeterministic .

Formal definition

The Moore automaton can be defined as a 7- tuple : ${\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\Omega ,\delta ,\lambda ,q_{0},F\right)}$

1. ${\displaystyle Q}$is a finite set of states . ${\displaystyle \left(\left|Q\right|<\infty \right)}$
2. ${\displaystyle \Sigma }$is the input alphabet. , ${\displaystyle \left|\Sigma \right|<\infty }$ ${\displaystyle Q\cap \Sigma =\emptyset }$
3. ${\displaystyle \Omega }$ is the output alphabet. ${\displaystyle \left|\Omega \right|<\infty }$
4. ${\displaystyle \delta }$ is the transition function ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$
5. ${\displaystyle \lambda }$ defines the output function: ${\displaystyle \lambda :Q\rightarrow \Omega }$
6. ${\displaystyle q_{0}\in Q}$ is the start state.
7. ${\displaystyle F\subseteq Q}$is a (finite) set of possible accepting states (= final state set). If the automaton stops in one state after reading the input word , it is part of the language . ${\displaystyle J\in \Sigma ^{*}}$ ${\displaystyle F}$ ${\displaystyle J}$ ${\displaystyle L\left(A\right)}$

If the regular language of the machine is of no interest, it can also be left out. Then the automaton is defined as a 6-tuple. ${\displaystyle F}$

The number of states of a Moore machine is not less than the number of states of the corresponding Mealy machine .

Digital technology

Moore machine in digital technology

The Moore machine can be implemented using digital technology. This requires two switching networks and a clocked memory block. In addition to the logic modules wired on a circuit board, the implementation is often carried out using programmable logic and the use of a hardware description language .

Processing with logic circuits requires the conversion of the input and output alphabet into a binary code analogous to the table below.

Coding

Input alphabet e 0 e 1 e 2 x 0 1 0 y 0 0 1 ... ... ... ...

State quantity d 0 d 1 d 2 q 0 1 1 0 q 1 1 0 1 ... ... ... ...

Output alphabet a 0 a 1 a 0 1 b 1 0 ... ... ...

Description of a machine

Given a by a 6-tuple defined, deterministic finite automaton with ${\displaystyle \left(Q,\Sigma ,\Omega ,\delta ,\lambda ,q_{0}\right)}$

${\displaystyle Q=\lbrace q_{0},\,q_{1},\,q_{2},\,q_{3}\rbrace }$,

${\displaystyle \Sigma =\lbrace x,\,y,\,z\rbrace }$,

${\displaystyle \Omega =\lbrace a,\,b,\,c\rbrace }$

and . ${\displaystyle q_{0}=q_{0}}$

The transition function and the output function can be represented by a graph or a machine table. ${\displaystyle \delta }$ ${\displaystyle \lambda }$

Description of a machine

${\displaystyle \delta }$ (Transition) ↘    ${\displaystyle x}$      ${\displaystyle y}$      ${\displaystyle z}$   ${\displaystyle \lambda }$ (Output) q 0 ${\displaystyle q_{3}}$ ${\displaystyle q_{3}}$ ${\displaystyle q_{1}}$ ${\displaystyle b}$ q 1 ${\displaystyle q_{3}}$ ${\displaystyle q_{2}}$ ${\displaystyle q_{3}}$ ${\displaystyle a}$ q 2 - ${\displaystyle q_{3}}$ - ${\displaystyle a}$ q 3 ${\displaystyle q_{3}}$ - ${\displaystyle q_{2}}$ ${\displaystyle c}$

Representation of and through graphs ${\displaystyle \delta }$ ${\displaystyle \lambda }$

Representation of and by the machine board ${\displaystyle \delta }$ ${\displaystyle \lambda }$

Information such as the following can now be found in both the graph and the table:

If the machine is in the state and reads in the character "x" or the character "z" from there, the machine goes into the state . When the status is reached, "c" is output. ${\displaystyle q_{1}}$ ${\displaystyle q_{3}}$ ${\displaystyle q_{3}}$

Transfer to a Mealy machine

Every Moore machine can be easily converted into an equivalent Mealy machine . To do this, the output symbol of the input state only has to be written to the transition (state transition). If we look at the above example, the overpass looks like this:

Medvedev machine

→ Main article : Medvedev automaton

Graphic of a Medvedev machine

The Medvedev automaton is a special form of the Moore automaton, in which the states directly form the output, i.e. there is no output network. So every Medvedev machine is a Moore machine, but not the other way around. The name comes from Ju. T. Medvedev , who attached his own article to a translation of Automata Studies into Russian .

advantages

• The output delay is smaller.
• The clock edge of the flip-flops can be made smaller.

See also

• Automata theory
• Mealy machine
• Medvedev machine
• Deterministic finite automaton
• Nondeterministic finite automaton

literature

• Gottfried Vossen, Kurt-Ulrich Witt: Basic course in theoretical computer science . An application-oriented introduction. Vieweg + Teubner, Wiesbaden 2011, ISBN 978-3-8348-1537-8 ( limited preview in the Google book search).