Moore Machine

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:

• The states are $\{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.