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:
- For every state with distinct outputs on incident edges, split it into as many states as number of distinct outputs
- Associate the edge output with the state
- Redirect the edge appropriately
- 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:
- In case of Mealy to Moore, the output was postponed, but in case of Moore to Mealy, the output would be preponed
- 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
- 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.
What is meant by Incident Edges ??
Incident Edges are the cords coming on to the states.
wrong answer…
Dear Bijay,
As per my knowledge, I have given the correct answer. If you feel that it is wrong, then please rectify it and give the correct answer.
Hello!
Nice tutorial. Just a question. I found in literature and on the Internet, that the outputs of a state at a Mealy state diagram are placed on the outgoing edges of the states rather than on the incoming (incident) edges as you show. Is it correct?
Hi Manos,
It’s correct. The output can be on both outgoing as well as on incoming edges. Or I would say it should be on both the edges. Since the edges indicate the transition from a particular state to another state and the output shows the result of that particular transition.
Yes, indeed.
But as I understand, placing the outputs of a state on its incoming edges infers that the outputs are registered and that a look-ahead logic is used so that the outputs will be correct.
On the other hand, placing the outputs of a state on its outgoing edges infers that the outputs are not registered.
Am I understaning right? If so, then the two different Mealy designs may result to different Moore to Mealy transformations as the state minimization will be different.
Maybe I am overcomplicating this.
Anyway, thanks for the article and your response. 🙂
Dear Manos,
Can you please elaborate your concern. I mean in detail (registered and unregistered output).
Don’t we have initial state in converting one machine to another..?
You always need an initial state while designing a state machine. But while you are converting a state machine from one model to another (i.e, mealy to moore or vice versa), then you have already an initial state in the design.
In mealy machine ,as soon as the input bit is one..the output will become logic high.It need not go into another state. Now let us see for Moore machine … It is in the state which recognised the bit equence of 10 and state output is low. …
As we studied in many books that While converting from Moore to Mealy machine the number of states remains same for both Moore and Mealy machine,
So what if we don’t merge and.