Difference Between Mealy and Moore Machine
Both Mealy and Moore Machines accept the regular languages and provide the output. Before proceeding to the key difference between Mealy and Moore Machine, Let’s look at an example of the Mealy and Moore machines which helps us to understand all the key differences in the Mealy and Mealy machine
Moore Machine Example: The following is a Moore Machine which gives the first compliment of binary digit.
Mealy Machine Example: The following is a Mealy Machine which gives the first compliment of binary digit.
Key Difference Between Mealy and Moore Machine
Let’s explain all the major key differences between Mealy and Moore’s machine according to the above given diagram. A detailed description is given below
1. Transition Labels
Moving from one state to another state using an arrow is called a transition, and the value attached to the arrow is called a transition label.
- In a Mealy Machine, the transition label contains the input with the output represented as input/output (i.e., 1/a) or input, output (i.e., 1, a).
- In Moore Machine, the transition label contains only the input. Output remains inside the states instead of over the transition.
The discriptive diagram above transition labels is given below
2. Single State Behaviour
Single-state behaviour is different in Moore and Mealy machine.
- In a Mealy machine, A single state can generate any outputs (i.e., A, B, C, D, etc) against any inputs.
- In the Moore machine, A single state can generate only a fixed single output for all inputs.
The following diagram explains the difference of single state beharioour in Moore and Mealy Machines in detail
3. Output Function
In Mealy Machine Output Function (λ ) is
λ : Q × Σ → O
Where,
Qis
current stateΣ
is current input symbolO is
resulting output symbol
So, in a Mealy machine, the output is calculated during transitions, based on the current state and input.
In Moore Machine Output Function (λ) is
λ : Q → O
where,
Q is
current stateO is
resulting output symbol
So, in a Moore machine, the output is tied to each state and remains constant while in that state, regardless of the input.
4. Output Dependency
In a Mealy machine,
- Output depends on both the current state and the current input.
- Output can change immediately when the input changes, even without a state change.
In a Moore machine,
The output depends only on the current state, regardless of the input. It changes only when the machine moves to a new state.
5. Output Length
The output length is different in Mealy and Moore for the same output.
Mealy Machine Output length = input length
Reason: In a Mealy machine, the output is based on the current state and the current input symbol. So, when the machine starts, it enters the initial state, but no output is produced yet. As it reads the first input symbol, the transition occurs and generates an output. So, the first output comes with the first input.
Moore Machine Output length = input length + 1
Reason: In a Moore machine, each state holds an output, and the machine enters the start state before any input is read. Since the output is based only on the state (not on the input), the machine produces the first output immediately, without consuming any input.
Let’s consider the Moore and Mealy Machines, and we get output from these examples by using a specific input
The following figure explains the output length for input “1101” in Moore and Mealy Machines
Important: In many cases, application designers align the output length of a Moore machine with its input length by ignoring or discarding the first output in practical applications.
6. Number of States After Conversions
When converting between Mealy and Moore machines, the number of states may change, which depends on the direction of conversion.
Mealy to Moore Conversion
In a Mealy machine, a single state can produce different outputs for different inputs. When converting Mealy to a Moore machine, we must create separate states for each unique output behavior.
-
Result: Number of states increases in most cases.
The following figure explains how the number of states increases when converting from Mealy to Moore.
Moore to Mealy Conversion
In a Moore machine, each state has a fixed output. When converting Moore to Mealy machine, we can merge multiple Moore states into one if their transitions lead to the same output behavior.
Result: The Number of states may reduce.
7. Number of States for Equivalent Functionality
To implement the same functionality, a Moore machine usually requires more states than a Mealy machine.
-
Mealy Machine can change output on transitions, so it can handle multiple output behaviors within a single state.
-
Moore Machine produces output only on states, so for every unique output, a separate state is needed. Therefore, a Moore machine may need to split a single Mealy state into multiple states, each with different outputs.
The following figure explains how the number of states can be changed in Moore and Mealy for equivalent functionality.
8. Output Synchronization
Synchronization makes sure outputs and transitions follow the clock cycle, avoiding mid-cycle changes or instability.
One clock cycle completes when
- The system reads the current input,
- Processes the transition (based on current state and input),
- Moves to the next state
- And produces the output
Moore Machine (One Clock Cycle Working)
I) At the start of the clock cycle:
-
The machine is in a current state.
-
It outputs the value associated with that state.
II) During the clock cycle:
-
It reads the input, decides the next state.
III) At the rising edge of the clock:
-
The machine transitions to the next state.
-
New output appears in the next cycle (from the new state).
Output is updated only at the end of the cycle, after the state change.
Mealy Machine (One Clock Cycle Working)
I). At the start of the clock cycle:
-
The machine is in its current state.
-
It reads the input immediately.
II). During the same cycle:
-
It calculates the next state.
-
It generates the output based on the current input and state.
III). At the clock edge:
- The machine moves to the next state, ready for the next input.
Output is generated instantly within the cycle, not delayed to the next.
Result:
|
9. Responsiveness
A machine that provides output immediately is considered more responsive. A Mealy machine is more responsive than a Moore machine
Reason:
In Mealy, as the machine reads the input, it immediately provides the output because the transition label shows the relation of input to output.
In Moore as the machine reads the input, it first goes to the next state and then provides the output. So output appeared with a step delay as compared to the Mealy Machine.
The following figure explains the responsiveness in Moore and Mealy Machines
10. Machine Design Complexity
When comparing Mealy and Moore machines, the design complexity primarily depends on how outputs are generated from states and inputs.
-
Mealy machines are generally less complex to design because they require fewer states—outputs depend on both state and input, so multiple output behaviors can be handled within a single state.
-
Moore machines tend to be more complex with more states, since each state must represent a unique output regardless of input, increasing the number of states needed.
The following figure explains the complexity of designing Moore and Mealy machines
Summary Table: Difference Between Mealy and Moore Machine
Key Point | Mealy Machine | Moore Machine |
State Diagram Labels | Transitions are labeled with both input and output. | Transitions are labeled with input only and output is associated with states. |
Input and Output String Length | If the length of the input string is “N”, then the length of the output string is also “N” | If the length of the input string is “N”, then the length of the output string is “N+1”. |
Output Function | ‘λ’ is the output function which maps Q×∑→ O. Where Q is state, and O is output. | λ is the output function which maps Q → O. Where Q is state, and O is output. |
Output Dependency | Output in Mealy Machine is placed in each transition. That’s why it depends on the present state as well as the present input. So, If input changes, output also changes because output depends on State and input. | Output in Moore Machine is placed within each state. That’s why it depends only on the current state. So, If input changes, output does not change because output depends on only State. |
Output States after conversions | The number of states can increase after conversion from Mealy to Moore machine. | After conversion from Moore to Mealy machine, state numbers always decrease. |
Output synchronization | Output is not synchronized with the clock. Mealy Machines react faster to inputs. | Output is synchronized with the clock. Moore Machines react slower to inputs (1 clock cycle later). |
Responsiveness: | More responsive to inputs since the output can change as soon as the input does. | Less immediate response; outputs change only when the state changes. |
Number of States for Equivalent Functionality: | Often requires fewer states than Moore to achieve the same function. | May require more states to represent different outputs for the same set of inputs. |
Machine Designing | It is more complex to design due to the direct input-output relationship. | It is less complex in design because outputs are fixed per state. |