Mealy to Moore Conversion

Mealy to Moore Conversion is slightly more complex than the conversion of Moore to Mealy machine. In a Mealy machine, the output depends on both the current state and the input, whereas in a Moore machine, the output is determined only by the current state. The following diagram represents the transition diagrams of Mealy and Moore machines.

In this lecture, we convert the Mealy Machine Transition diagram and transition table into an equivalent Moore Machine Diagram and transition table. First, look at some rules for Mealy to Moore conversions 

Mealy to Moore Transition Diagram Conversion

Two basic rules can be defined from conversions of Mealy’s transition diagram to Moore’s transition diagram.

Rule 01: No State Duplicated

When every input that enters a Mealy state produces the same output. Then, simply place that output within that particular state of the Moore machine. In this case,  that particular state is not duplicated.

For Example, let’s discuss an example of case 01

• Mealy Machine: When entering inputs are 5 (“0”, “0”, “1”, “0”, “1”) with all  similar outputs (i.e., “A”) in a particular state (i.e., say state “q2”)
• Moore Machine: In Mealy to Moore conversion, Particular State “q2” is not duplicated (because all provide similar outputs).

Rule 02: States Duplicated

When some Inputs are entered in any particular Mealy state, with different types of outputs, we cannot represent more than one output in one state of the Moore Machine. In this case, that particular state is duplicated “n” times, where “n” represents how many output types. 

For example, let’s discuss an example of case 02 where “n = 3”

• Mealy Machine: When entering inputs are 5 (“0”, “0”, “1”, “0”, “1”) with 3 different outputs (i.e., “A”, “B”, “C”) in a particular state (i.e., say state “q2”)
• Moore Machine: In Mealy to Moore conversion, Particular State “q2” is duplicated 3 times (because outputs are 3 types), where new states become “q2A”, “q2B”, and “q2C” for output “A”, “B”, and “C” respectively.

Mealy to Moore Transition Table Conversion

There are two basic rules that can be defined from conversions of Mealy’s transition table to Moore’s transition Table.

Rule 01: No State Duplicated

When a particular state appears once or more than once in the “input column” with a similar output of the Mealy Transition Table, then that particular state also appears the same in the Moore Transition Table (never duplicated).

Example: In the following transition table, both input columns (for “0” and “1”) display the next state along with the output.

• All “q0” states, either in input “0” or “1” columns, contain output “A” (mentioned as qo, A)
• All “q1” states, either in input “0” or “1” columns, contain output “B” (mentioned as q1, B)
• All “q2” states, either in input “0” or “1” columns, contain output “C” (mentioned as q2, C)
• All “q3” states, either in input “0” or “1” columns, contain output “A” (mentioned as q3, A)
• All “q4” states, either in input “0” or “1” columns, contain output “B” (mentioned as q4, B)
• All “q5” states, either in input “0” or “1” columns, contain output “A” (mentioned as q5, A)

So, the No Input state in the input columns holds different types of output.  The following figure shows all

Rule 02: State Duplicated

When a particular state appears more than once in the input column with different outputs (i.e,. “A”, B etc) of the Mealy Transition Table, then that particular state will always be duplicated “n” times in the Moore Transition Table, where “n” represents how many types of output. 

Example: In the following transition table, both input columns (for “0” and “1”) display the next state along with the output. All “q0” states, either in input “0” or “1” columns, contain output “A” (mentioned as qo, A). No “q0” state is duplicated. All “q1” states, either in input “0” or “1” columns, contain output “B” (mentioned as q1, B). No “q1” state is duplicated. All “q2” states, either in input “0” or “1” columns, contain output  “A” and”C” (mentioned as q2, A, q2, C). So, “q2” is duplicated. All “q3” states, either in input “0” or “1” columns, contain output “B” and “C” (mentioned as q3, B and q3, C). So,  “q3” is duplicated. All “q4” states, either in input “0” or “1” columns, contain output “C” (mentioned as q4, C).  No “q4” state is duplicated. So, the No Input state in the input columns holds different types of output.  The following figure shows all

Let’s explain some examples of Mealy to Moore Machine Conversions along with their transition tables

Example 01: Mealy to Moore Conversion

Consider the following Mealy Machine

As in the above Mealy Machine,

• q0 is the start state, (0,1) are inputs, and “a” is the output.
• Every entering input in the state q0 having the similar output “a”.
• So, simply cut the output “a” over the arrow and place it along with the state “q0”.

After conversion, the Moore Machine is given under

The transition table for the Mealy to Moore conversion is given below

Example 02: Mealy to Moore Conversion

Consider the following Mealy Machine

At point q0,

There is no arrow entering into the state q0. So, the output for the q0 is null. As given Below

At point q1,

There are three arrows entering into the state q1. Arrows from q0 and q1 have the input “0” with output “a”, and Arrow from q2 has the input “1” with “b” output.

Output of 2 types (a,b) enter state q1, So One duplicate of q1 is generated with a different outputs.

So, the output of type “a” is placed along with state q1. The output of type “b” is placed along with the duplicated state (q1) as given below.

Further Proceeding above, Now transitions from both states (original q1 and duplicate q1) for inputs 0 and 1.

• For input “0” transition goes to q1 for output “a”.
• For input “1”, the transition goes to q2 for output “b”.

As given below

Now, the remaining state is only q2, which has to be discussed.

There are three arrows entering into the state q2. Arrows from q0 and q2 (itself) have the input “0” with output “a”, and Arrow from q2 has the input “1” with “b” output.

Output of 2 types (“a” and “b”) enter into state q2, So One duplicate state of q2 is generated.

By completing the transition from both states (original q2 and duplicate q2) for inputs 0 and 1, the final Mealy machine is given below.

Important: After State duplication in the transition diagram q1 is named as q1a and q1b, Similary, q2 is named as q2a and q2b

Mealy to Moore conversion, the transition table for the given example is given below

Example 03: Mealy to Moore Conversion

In this example,

• Mealy Machine: Two inputs “0” and “1” with different outputs “A” and “B” enter into a state “q0”.
• Moore Machine: State “q0” is duplicated where new states become “q0A” and “q0B” for output “A” and “B” respectively

as shown in the following diagram.

Mealy to Moore conversion, the transition table is given below

Example 04: Mealy to Moore Conversion

In this example,

• Mealy Machine: Two inputs (“0” and “1”) with different outputs (“A” and “C”) enter into a state “q2”.
• Moore Machine: State “q2” is duplicated where new states become “q2A” and “q2C” for output “A” and “C” respectively

As shown in the following diagram.

Mealy to Moore conversion, the transition table is given below

Example 05: Mealy to Moore Conversion

In this example, for state “q2”

• Mealy Machine: Two inputs (“0” and “1”) with different outputs (“A” and “C”) enter into a state “q2”.
• Moore Machine: State “q2” is duplicated twice where new states becomes “q2A” and “q2C” for output “A” and “C” respectively

Similarly, for state “q3”

• Mealy Machine: Three inputs (“0″, 0” and “1”) with two different types of outputs (“B” and “C”) enter into a state “q3”.
• Moore Machine: State “q3” is duplicated twice where new states becomes “q3B” and “q3C” for output “B” and “C” respectively

As shown in the following diagram.

Mealy to Moore conversion, the transition table is given below

Example 06: Mealy to Moore Conversion

In this example, for state “q2”

• Mealy Machine: Three inputs (“0”, “0” and “1”) with three different outputs (“A”, “B” and “C”) enter into a state “q2”.
• Moore Machine: State “q2” is  duplicated (3 times) where new states becomes “q2A”, “q2B” and “q2C” for output “A”, “B” and “C” respectively

As shown in the following diagram.

Mealy to Moore conversion, the transition table is given below

Example 07: Mealy to Moore Conversion

In this example, for state “q4”

• Mealy Machine: Four inputs (“0”, “1”, “1”, and “1”) with four different outputs (“A”, “B”, “C”, and “C”) enter into a state “q4”.
• Moore Machine: State “q2” is  duplicated (4 times) where new states become “q4A”, “q4B”, “q4C”, and “q4D” for output “A”, “B”, “C”, and “D” respectively

As shown in the following diagram.

Mealy to Moore conversion, the transition table is given below

Examination-Based Question

In examination-based questions related to Mealy to Moore machine conversion, a possible case to solve is one of the following.

• Mealy Machine Diagram  → Moore Machine Diagram
• Mealy Transition Table → Moore Transition Table
• Mealy Machine Diagram → Mealy Transition Table → Moore Transition Table → Moore Diagram

Important. If “M” is the number of states and “N” is the number of outputs in the Mealy Machine, then the maximum number of States in the Mealy Machine will be “M” multiplied by “N”. Suppose if 3 number of states and 2 number of outputs in Mealy, then 6 will be the maximum state in Moore Machine.