In the Theory of computation, there is an important concept, finite state machine. It is a model of computation that is used to design systems. The finite state machine has a finite set of states and it changes states according to the transition function(δ) and processes inputs and produces output based on the output function(𝜆).
Here we will be discussing Mealy to Moore conversation that is commonly used in the Theory of computation.
What is Mealy Machine?
Mealy Machine is a finite state machine whose output depends on the present state and corresponding input value. Mealy Machine is defined as (Q, q0, 𝛴, O, δ, 𝜆) where
Conversion of Mealy Machine to Moore Machine using TOC
In a Moore machine, each of the states is associated with an output, while in a Mealy machine, the output is associated with transitions along with input symbols.
In order to convert a Moore machine to a Mealy machine, we need to distribute state output symbols along with the input symbol paths. Also, we have to create distinct states for each new output symbol and distribute them according to incoming and outgoing edges.
The following steps are used for converting the Mealy machine to the Moore machine:
Step 1 - In this conversion process we split a state q of the Mealy machine with several states, the number of such states is equal to the number of different outputs associated with state q.
Step 2 - After adding extra states, when we find output associated with state q is the same everywhere in the table, we add the output as the output of the state q (i.e In the Moore machine output depends only on the present state).
Step 3 - After splitting the columns, we get an equivalent Moore Machine.
Consider the below transition table of a Mealy machine whose transition diagram is given above:
Input=0 Input=1
Present State
Next state
Output
Next State
Output
q0
q2
b
q1
b
q1
q3
b
q2
b
q2
q2
b
q2
b
q3
q2
b
q0
a
For state q0, we can find only a is associated-output with state q0 in the 4th row.
So, q0 → a
for, state q1, we can find only b associated output with state q1 in the 1st row. So, q1 → b
Similarly, we can find
q2 → b
q3 → b
So, the transition table of the corresponding Moore Machine
Below is an example to illustrate the process of Converting a Mealy machine to a Moore machine:
Original Mealy Machine:
States: A, B, C
Inputs: 0, 1
Outputs: 0, 1
Transition Table:
State
Input
Next State
Output
A
0
B
0
A
1
A
1
B
0
A
0
B
1
C
1
C
0
B
0
C
1
A
1
Conversion to a Moore Machine:
Create new states based on unique output conditions
Update the transition table accordingly:
State
Input
Next State
State Output
A
0
B
0
A
1
A
1
B
0
A
0
B
1
C
1
C
0
B
0
C
1
A
1
In the above conversion, we have introduced new states to represent unique output conditions that are 0 and 1. The state outputs are determined solely by the state, making it a Moore machine. This conversion simplifies the machine by removing input-dependent outputs.
What is the relationship between a Mealy machine and a Moore machine?
The relationship between them is that they both are finite state machines and differ in how they determine their output. Mealy machine's output depends on both its current state and the input it receives, while a Moore machine's output depends solely on its current state.
Which is easier Moore or Mealy?
Moore's machine is easier in comparison to more machines. Because their outputs depend only on the current state, they are much easier to design and understand.
What is Moore and Mealy output?
In a Moore machine, the output is dependent only on the current state which means each state has a predetermined output. On the other hand, in a Mealy machine, the output depends on both the current state and the input which results in more flexible and input-dependent output behaviour.
How is a Mealy Machine different from a Moore Machine?
A Mealy machine is a finite state machine whose output depends on the current state as well as the corresponding input value however a Moore machine is a finite state machine whose output depends only on the present state.
Conclusion
This article covered an important concept of how a Mealy Machine is converted into a Moore Machine using a transition table.
116+ registered 