Moore Machine | Sahithyan's Notes

A finite state transducer where output depends only on the current state. A 6-tuple.

$M = (Q, \Sigma, \Delta, q_0, \delta, \lambda)$ where:

$Q$ is a finite set of states
$\Sigma$ is the input alphabet
$\Delta$ is the output alphabet
$q_0 \in Q$ is the initial state
$\delta : Q \times \Sigma \rightarrow Q$ is the transition function
$\lambda : Q \rightarrow \Delta$ is the output function (state $\to$ output symbol)

Output is associated with states, not transitions. On input of length $n$ , the output sequence has length $n + 1$ (one output per state visited, including the initial state).

Example

A Moore machine that outputs $E$ when the number of $a$ s seen is even and $O$ when odd:

States: $\{q_0, q_1\}$ with $\lambda(q_0) = E$ , $\lambda(q_1) = O$
$\delta(q_0, a) = q_1$ , $\delta(q_1, a) = q_0$

Starting in $q_0$ , input aaa visits $q_0, q_1, q_0, q_1$ and outputs EOEO.

Conversion from FA

Every FA has an equivalent Moore machine recognizing the same language.

For FA $M = (Q, \Sigma, q_0, A, \delta)$ , construct Moore machine $M' = (Q, \Sigma, \{0,1\}, q_0, \delta, \lambda)$ where:

$\lambda(q) = 1$ if $q \in A$ , else $\lambda(q) = 0$

Conversion to Mealy Machine

Every Moore machine has an equivalent Mealy machine. For each transition $\delta(q, a) = p$ , create a Mealy output $\lambda_M(q, a) = \lambda(p)$ (copy the Moore output of the destination state onto the transition).

The resulting Mealy machine has the same states but produces output on transitions instead of states.