How to convert the Mealy machine to the Moore machine

Mealy machines can be converted to Moore machines with a few simple steps.

Note: You can learn more about Moore machines and Mealy machines.

Conversion techniques

There are two techniques to convert these machines:

• By transition diagram

• By transition table

Let's take examples of both these techniques.

By transition diagram

The steps involved in this method are:

1. Select the initial state and draw the transitions by adding the output symbol of that transition to the destination state.

2. Repeat the process for every single transition.

3. If a conflict occurs, that is, if a state requires to give two different outputs, make a duplicate state.

4. Add transitions for all duplicate states on all input symbols.

Example

Let's take a simple Mealy machine:

1. We take the initial state and draw its first transition:

The transition had an output $b$ , that is now transferred to our destination node $q_1$. Now, for the second transition of state $q_0$:

2. We repeat the process:

3. We encounter a conflict on the transition $q_1 \to q_1$ as it has an output $a$ , but the state $q_1$ already has an input $b$. So we make a duplicate state:

4. Now we add transitions to the new state:

For example, we know from the Mealy machine that $q_1$ at $0$ goes to $q_0$ and gives an output $a$, so we use the same logic to form the new transition.

Our final Moore machine is shown in the image above.

By transition table

The steps involved in this method are:

1. Find the states that have more than one output associated with them in each column. For such states, divide them into two.

2. Rewrite the transition table, including the new states, and add an output column. Then, fill in the destination state entries using the original table.

3. Check for the output of each state in the destination column and fill in the output column.

4. Remove the output symbols from the destination columns.

Example

Let's take the transition table of the previous example:

1. We see that in the destination columns, the state $q_1$ has two different outputs for the input symbols; hence we will make them into two states $q_{1a}$ (q1 with output $a$) and $q_{1b}$ (q1 with output $b$).

2. Now let's form the transition table:

For example, the transition of $q_0$ on $0$ is towards $q_1$ in the Mealy machine, but in this case, we have split $q_1$ in two states. As a result, we see the corresponding output of that transition. In this case, the output is $b$; therefore, the destination will be $q_{1b}$.

3. Now we fill in the output column:

For example, the $q_0$ state has the output $a$ in both columns of the destination; thus, the final output is also $a$.

4. Remove the output from the destination columns:

The table above is the final Moore machine.

Conclusion

While transforming a Mealy machine having $n$ states and $m$ outputs, there can be at most $n \times m$ states in the Moore machine.