What is a Moore machine?

Overview

A Moore machine is a finite state machine that has an output value rather than a final state. For a given input, the machine generates a corresponding output. The output of the Moore machine depends only on the present state of the FA.

Unlike other finite automata that determine the acceptance of a particular string in a given language, Moore machines determine the output against given input.

Formal theorem

The Moore machine is a 6 tuple machine $(Q, \Sigma, q_0, \Delta, \delta, \lambda)$:

$Q$: This is a set of states.

$\Sigma$: This is a set of input alphabets.

$q_0$: This is the initial state.

$\Delta$: This is a set of output states.

$\delta$: This is a transition function, that is: $Q \times \Sigma \to Q$

$\lambda$: This is an output function, that is: $Q \to \Delta$

Note: The output function means that for every state there is a corresponding output associated with it.

Formation of the machine

The Moore machine forms an FA of the type:

In the machine above, the transition on input $i$ will give an output $y$ from the state $q_0$. Moreover, from $q_1$ a transition on input $j$ will provide an output $x$.

Note: If the input string is of length $n$, the output produced by a Moore machine will be of length $n+1$.

Example

Suppose we have the following Moore machine:

Now, we take an input string in $\Sigma \{0,1\}$ and see its output in $\Sigma \{a,b\}$. Let's take $x=1101$

Transitions explanation

• Our Moore machine starts from $q_0$. Without consuming any input, it will produce an $a$.

• The first input character is $1$. Hence, we move to $q_1$ and output a $b$. Our output string is $ab$.

• For the next $1$, we move to $q_0$, which outputs an $a$. The output string becomes $aba$.

• The next $0$ gives another $a$. The output string becomes $abaa$.

• The last $1$ takes us to $q_1$ and produces a $b$. The final output string is $abaab$.

Transition table

The transition table for the above machine will be:

A transition table contains all the properties of a Moore machine. As a result, it can also be used to form a Moore machine.

Note: To learn about a faster type of output generating machine, the Mealy machine, click here.