Mealy to Moore and Moore to Mealy Transformation

Sequential machines can be designed in two different ways: (i) Mealy Machine & (ii) Moore Machine

Considering Mealy or Moore for the designing of sequential machine, it’s actually difficult to draw a hard line where one machine is always better than the other. Depending on the application requirement one may dominate the other. It is very important to learn the transformation from one machine to another for the same design, so that required implementation can be done according to the demand.

---

Click here to know more about Mealy and Moore Machines

---

Mealy to Moore Transformation

Follow the below steps to transform a Mealy machine to a Moore machine:

1. For every state with distinct outputs on incident edges, split it into as many states as number of distinct outputs
2. Associate the edge output with the state
3. Redirect the edge appropriately
4. Define the new edges from the split states as per the original Mealy machine

Example

Following is an example of Mealy machine. We would learn how to convert this Mealy to its equivalent Moore machine.

• There is only one incident edge with output “0” on state S0. So, no splitting of state in Moore machine. Let’s S0(Mealy) ⇒ S0(Moore)
• There are 2 incident edges with outputs “1” and “0” on state S1. So, splitting needed in Moore machine. Let’s S1(Mealy) ⇒ For Moore S10{with output “0”} and S11{with output “1”}
• There are 2 incident edges with outputs “1” and “0” on state S2. So, splitting needed in Moore machine. Let’s S2(Mealy) ⇒ For Moore S20{with output “0”} and S21{with output “1”}

Now you can match the color of the transition lines in both Mealy and Moore and realize why some of the lines are split and some are not. Any doubt, please drop a comment below.

Moore to Mealy Transformation

Follow the below steps to transform a Mealy machine to a Moore machine:

1. In case of Mealy to Moore, the output was postponed, but in case of Moore to Mealy, the output would be preponed
2. The output associated to a particular state is going to get associated with the incident transition arcs. In the Mealy model the output will go to the edges rather than the states
3. Here we have to notice the states which can merge actually. For this we have to check whether are there states for the same input, they are going to the same next state.

Example

Following is an example of Moore machine. We would learn how to convert this Moore to its equivalent Mealy machine.

• In the above Moore machine “A” and “D” are two states which can be merged to a single state as we can see for both the states for same input the next state is same.
  • For input “1”, next state is “C” for both the present states “A” and “D”
  • For input “0”, next state is “B” for both the present states “A” and “D”

Here we can see that states “A” and “D” are merged to a single state AD’. Now you can match the color of the transition lines in both Moore and Mealy and realize why some of the lines are merged and some are not. Any doubt, please drop a comment below.