Conversion From Moore Machine to Mealy Machine
Let us take the Moore machine of Figure 1 and its transition table is shown in Table 3.
Step 1. Construct an empty mealy machine using all states of the Moore machine as shown in Table 4.
Input=0 | Input=1 | |||
Present State | Next State | Output | Next State | Output |
q0 | ||||
q10 | ||||
q11 | ||||
q20 | ||||
q21 |
Table 4
Step 2: Next state for each state can also be directly found from Moore machine transition Table as:
Input=0 | Input=1 | |||
---|---|---|---|---|
Present State | Next State | Output | Next State | Output |
q0 | q10 | q20 | ||
q10 | q10 | q21 | ||
q11 | q10 | q21 | ||
q20 | q11 | q20 | ||
q21 | q11 | q20 |
Table 5
Step 3: As we can see output corresponds to each input in the Moore machine transition table. Use this to fill the Output entries.
Example: Output corresponding to q10, q11, q20 and q21 are 0, 1, 0 and 1 respectively.
Input=0 | Input=1 | |||
---|---|---|---|---|
Present State | Next State | Output | Next State | Output |
q0 | q10 | 0 | q20 | 0 |
q10 | q10 | 0 | q21 | 1 |
q11 | q10 | 0 | q21 | 1 |
q20 | q11 | 1 | q20 | 0 |
q21 | q11 | 1 | q20 | 0 |
Table 6
Step 4: As we can see from Table 6, q10 and q11 are similar to each other (same value of next state and Output for different Inputs). Similarly, q20 and q21 are also similar. So, q11 and q21 can be eliminated.
Input=0 | Input=1 | |||
---|---|---|---|---|
Present State | Next State | Output | Next State | Output |
q0 | q10 | 0 | q20 | 0 |
q10 | q10 | 0 | q21 | 1 |
q20 | q11 | 1 | q20 | 0 |
Table 7
This is the same mealy machine shown in Table 1. So we have converted Mealy to Moore machine and converted back Moore to Mealy.
Note: Number of statAes in the mealy machine can’t be greater than number of states in moore machine.
Example: The Finite state machine is described by the following state diagram with A as starting state, where an arc label is x / y and x stands for 1-bit input and y stands for 2-bit output.
Outputs the sum of the present and the previous bits of the input.
- Outputs 01 whenever the input sequence contains 11.
- Outputs 00 whenever the input sequence contains 10.
- None of these.
Solution: Let us take different inputs and its output and check which option works:
Input: 01
Output: 00 01 (For 0, Output is 00 and state is A. Then, for 1, Output is 01 and state will be B)
Input: 11
Output: 01 10 (For 1, Output is 01 and state is B. Then, for 1, Output is 10 and state is C)
As we can see, it is giving the binary sum of the present and previous bit. For the first bit, the previous bit is taken as 0.
Mealy and Moore Machines in TOC
Moore and Mealy Machines are Transducers that help in producing outputs based on the input of the current state or previous state. In this article we are going to discuss Moore Machines and Mealy Machines, the difference between these two machines as well as Conversion from Moore to Mealy and Conversion from Mealy to Moore Machines.