Mealy machines can be converted to Moore machines with a few simple steps.
Note: You can learn more about Moore machines and Mealy machines.
There are two techniques to convert these machines:
By transition diagram
By transition table
Let's take examples of both these techniques.
The steps involved in this method are:
Select the initial state and draw the transitions by adding the output symbol of that transition to the destination state.
Repeat the process for every single transition.
If a conflict occurs, that is, if a state requires to give two different outputs, make a duplicate state.
Add transitions for all duplicate states on all input symbols.
Let's take a simple Mealy machine:
We take the initial state and draw its first transition:
The transition had an output
We repeat the process:
We encounter a conflict on the transition
Now we add transitions to the new state:
For example, we know from the Mealy machine that
Our final Moore machine is shown in the image above.
The steps involved in this method are:
Find the states that have more than one output associated with them in each column. For such states, divide them into two.
Rewrite the transition table, including the new states, and add an output column. Then, fill in the destination state entries using the original table.
Check for the output of each state in the destination column and fill in the output column.
Remove the output symbols from the destination columns.
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 |
We see that in the destination columns, the state
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
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
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.
While transforming a Mealy machine having
Free Resources