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:

g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / a
An example Mealy machine
  1. We take the initial state and draw its first transition:

g ENTRY q0 q0 ENTRY->q0 q1/b q1/b q0->q1/b 0
Step 1: Draw first transition of the initial state

The transition had an output bb , that is now transferred to our destination node q1q_1. Now, for the second transition of state q0q_0:

g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 1 q1/b q1/b q0/a->q1/b 0
Step 1: Draw remaining transitions of the initial state
  1. We repeat the process:

g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 1 q1/b q1/b q0/a->q1/b 0 q1/b->q0/a 0
Step 2: Repeat the process
  1. We encounter a conflict on the transition q1q1q_1 \to q_1 as it has an output aa , but the state q1q_1 already has an input bb. So we make a duplicate state:

g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 1 q1/b q1/b q0/a->q1/b 0 q1/b->q0/a 0 q1/a q1/a q1/b->q1/a 1
Step 3: Add duplicate states when conflict occurs
  1. Now we add transitions to the new state:

g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 1 q1/b q1/b q0/a->q1/b 0 q1/b->q0/a 0 q1/a q1/a q1/b->q1/a 1 q1/a->q0/a 0 q1/a->q1/a 1
Step 4: Add transitions to the new state

For example, we know from the Mealy machine that q1q_1 at 00 goes to q0q_0 and gives an output aa, 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:

Current State

Destination State for 0

Output at 0

Destination State for 1

Output at 1

q0

q1

b

q0

a

q1

q0

a

q1

a

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

  2. Now let's form the transition table:

Current State

Destination State for 0

Destination State for 1

Output

q0

q1b, b

q0, a


q1a

q0, a

q1a, a


q1b

q0, a

q1a, a


For example, the transition of q0q_0 on 00 is towards q1q_1 in the Mealy machine, but in this case, we have split q1q_1 in two states. As a result, we see the corresponding output of that transition. In this case, the output is bb; therefore, the destination will be q1bq_{1b}.

  1. Now we fill in the output column:

Current State

Destination State for 0

Destination State for 1

Output

q0

q1b, b

q0, a

a

q1a

q0, a

q1a, a

a

q1b

q0, a

q1a, a

b

For example, the q0q_0 state has the output aa in both columns of the destination; thus, the final output is also aa.

  1. Remove the output from the destination columns:

Current State

Destination State for 0

Destination State for 1

Output

q0

q1b

q0

a

q1a

q0

q1a

a

q1b

q0

q1a

b

The table above is the final Moore machine.

Conclusion

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

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved