Conversion from Mealy Machine to Moore Machine
In this topic, we will see different ways that are used for the conversion of Mealy Machine to Moore Machine.
Moore Machine
The output of Moore machine depends only on the present state of the machine. In Moore Machine, if the input string is of length n, then the generated output string will be of length n+1.
Mealy Machine
In Mealy machine, value of output function depends on the current state and current input. In mealy machine, if the input string of length n, then the generated output string will also be of length n.
Methods used for conversion of Mealy Machine to Moore Machine
Following are the two methods that are used for converting a Moore Machine to Mealy Machine:
Converting a Mealy Machine to Moore Machine using transition diagram
In this method, we convert the Mealy Machine to Moore Machine using transition diagram of Mealy machine:
Following steps are used to convert Mealy Machine to Moore Machine:
Step1: Start from initial state q0.
Step2: Check how many edges are entering into that state.
Step3: If any edge has different output, then make copy of that state. Let say, one edge has output a, and another has output b, then we make the copies of state q0 to q0’/a and q0’’/b corresponding to the output a and b. As we have assumed that q0 is the start state, and we make copies of it, which means from initial state q0, we got two states q0’ and q0’’.
Now any one of them can be used as start state of Moore machine M, because they give identical direction for processing to other states.
Step4: If the edges have same output, then do not make copies, instead just remove output from edges and put the output in the state. Suppose two edges are entering in q0 have same output, say a, then we put the output a into state q0 and relabel it without output.
Step5: Now check if the state has a loop. If the sate loop is labelled with 1/b, then two copies of q0 (q0’/a and q0’’/b) are connected by an edge labelled 1 from q0’ to q0’’. Also add a loop labeled 1 on state q0’’.
Step6: If there are no edges entering into the state then we can assign it any output.
Step7: Repeat above steps for all other states.
Example
Convert the following Mealy machine to Moore machine using transition diagram.
Solution:
In this method, we will convert the mealy machine to Moore machine by using the transition diagram of mealy machine.
We start form initial state q0. Two edges are entering in this state. One edge is labelled 1/b, and another is labelled with 1/a. Therefore, we create two copies of q1, one is q1’ and second is q1’’ with output a and b respectively. State q1 also have loop, which means these copies are connected to each other by an edge labelled 1 from q1’ to q1’’ so that output is b. Also add a loop labelled 1 on state q1’. Connect these copies with state q2 through an edge labelled 0/a.
The partial Moore Machine is shown below:
We can make any state from q1’ and q1’’ as initial state, but we are selecting q1’. After applying same steps on partial Mealy machine, we got the following Moore Machine:
The final Moore machine is given below:
Converting a Mealy Machine to Moore Machine using transition table
We can convert a Mealy Machine to Moore Machine by using transition table of Mealy Machine. In this method, we split state q1 into transition table of Mealy machine with several states, the number of such states are equal to number of different outputs associated with q1. We split state q1, if it is associated with different outputs, otherwise leave this state as it is. After splitting the columns of the Mealy machine table, we get the Moore machine equivalent to Mealy machine.
Example:
Convert the following Mealy machine into Moore Machine.
Solution:
The equivalent transition table for Mealy Machine is given below:
Only state q0 in the table have different output, all other states have same output. So, we will split state q0 into two states q0’ and q0’’.
The modified table is shown below:
After rearranging the column, we get the following transition table for Moore machine.
source