Difference between Mealy and Moore Machine

Last Updated on March 21, 2023 by Prepbytes

Before digging deeper into the difference between Mealy and Moore Machines, we will first discuss what each machine does individually in this article. Then, we will discuss the different ways in which these machines vary from each other.

What is Finite State Machine?

There are two types of finite state machines Moore and Mealy, before diving deep into the difference between mealy and Moore machines let us first understand what are Finite State Machines (FSM). Finite State Machine is the simplest machine that is used to recognize patterns. It is an abstract computing device that has five tuples.

Formal Definition of Finite State Machine

It is defined as a set of five tuples or elements

M=(Q, Σ, δ, q0, F)
where,
Q: Finite set of states.
Σ: Finite set of alphabets called input symbols.
δ: Q × Σ → Q Transition function.
q0: Initial state.
F: Set of Final state.

There are two types of finite-state machines and the main difference between them is the way the output is generated in the machines.

1. Moore Machine
2. Mealy Machine

What is Moore Machine?

A finite state machine with an output symbol for each state is known as a Moore machine. The current state and current input symbol decide the next state in a Moore machine.

The present state of the machine determines the output symbol at a given time.

Moore machine consists of six tuples which are :

(Q, q0, Σ, O, δ, λ)

Where,

Q: Finite set of states.
q0: Initial state
Σ: Finite set of alphabets called input symbols.
O: Output alphabet.
δ: Transition function where Q × Σ → Q.
λ: Output function where Q → O.

Example 1

Design a Moore machine to generate 1’s complement of a given binary number.

Answer
The transition diagram is as follows −

Explanation:

• Step 1 – The start state q0 generates output 0 and transitions to q1 on input ‘0’, and transitions to q2 on input ‘1’.
• Step 2 – The state q1 generates output 1 and transitions to itself on input ‘0’, and transitions to q2 on input ‘1’.
• Step 3 – The state q2 generates output 0 and transitions to q1 on input ‘0’, and transitions to itself on input ‘1’.

For example, consider the binary number 1011.

Input

Input		1	0	1	1
State	q0	q2	q1	q2	q2
Output	0	0	1	0	0

The transition table is as follows −

What is Mealy Machine?

A Mealy machine is a machine in the theory of computation in which the output symbol is linked to the transition (state and input) of a finite state machine.
The present input symbol and present state of the machine determine the output symbol in a Mealy machine.

To represent the output in the Mealy machine, each input symbol is associated with an output and separated by a slash for each state.

We can describe the Mealy machine with six tuples (Q, q0, Σ, O, δ, λ’)

where:

• Q is a finite set of states.
• q0 is the initial state.
• Σ is a finite set of input alphabet.
• O is the output alphabet.
• δ is the transition function where Q × Σ → Q.
• λ’ is the output function where Q × Σ → O.

Example 2

Input − 11
Output − 00

The transition diagram is as follows −

Explanation:

• Step 1 – When we input ‘0’, the start state q0 transitions to state b and generates an output ‘0’. When we input ‘1’, q0 transitions to state q2 and generates an output ‘0’.
• Step 2 – When we input ‘0’, q1 transitions to itself and generates an output ‘0’. When we input ‘1’, q1 transitions to q2 and generates an output ‘1’.
• Step 3 – When we input ‘1’, q2 transitions to itself and generates an output ‘0’. When we input ‘0’, q2 transitions to state q1 and generates an output ‘1’.

The transition state table of a Mealy Machine is −

Characteristics of Mealy and Moore Machine:

Below given are the Characteristics of Mealy and Moore Machine-

Characteristics of Mealy Machine:

• A Mealy machine has lesser states than a Moore machine.
• It changes its output based on its present state and current input, and places the output on the transition.
• Mealy machines react to inputs faster than other machines, within the same clock cycle.
• When the input logic is done in the present state, the value of the output function becomes a function of transitions and changes.
• Designing a Mealy machine generally requires very few states, and the asynchronous generation of output through its state alters to synchronous on the present clock.
• The process of designing a Mealy machine requires little hardware, but it is not necessarily easy.

Characteristics of Moore Machine:

• A Moore Machine has more states than the Mealy Machine.
• The output of a Moore Machine depends only on its current state and is placed on the transition.
• Whenever the state changes, the output function’s value becomes a function of the current state and the changes at the edges of the clock.
• Both the state and output change synchronously with the clock edge.
• Designing a Moore Machine requires more hardware and more logic for decoding the output. This can lead to more delays in the circuit, which generally react after one clock cycle.
• Additionally, the states required for synthesis in a Moore Machine are also more.
• However, designing a Moore Machine is very easy. You can refer to a counter as a Moore Machine.

Difference between Mealy Machine and Moore Machine

The main difference between Mealy machine and Moore machine is in how they decide their outputs. Mealy machine theory of computation considers both the current state and inputs to make output decisions, while Moore machine theory of computation only considers the current state.

Let’s discuss the difference in the form of a table.

Mealy Machine	Moore Machine
For the same functions’ implementation, this machine requires fewer states.	This machine implements the same functions with a more significant number of states.
Designing this machine as a Mealy machine isn’t straightforward.	This is comparatively very easy to design Moore’s machine.
These machines respond to changes more quickly and all move in the same direction.	These machines usually react after one clock cycle, and decoding the output requires more logic, resulting in longer circuit delays.
Less hardware is required for design by this machine.	More hardware is required for design by this machine.
A counter can not be referred	Counter can be referred
When you create the input logic in the present state, transitions and changes make the output values a function..	Every time a change occurs in the state, the output value becomes a function of its current state and the changes at the edges of the clock.

Conclusion:
This article will help you to understand what is Finite State Machines and the difference between Mealy and Moore machines of finite state automata.In addition, you will also learn a deep understanding of Mealy and Moore Machines with examples.

FAQs

1. What is Turing Machine?
The computational model of a Turing machine, like Finite Automata (FA) and Pushdown Automata (PDA), operates on unrestricted grammar. When compared with FA and PDA, the Turing machine is the most powerful computational model.

We can formally define a Turing machine M as:

M = (Q, X, ∑, δ, q0, B, F)

Here, Q is a finite, non-empty set of states, X is the set of tape alphabets, and ∑ is the non-empty set of input alphabets. δ represents the transition function, q0 is the initial state of the machine,

2. As per the difference between Mealy Machine and Moore Machine, is a Mealy machine faster than a Moore machine?
Mealy machines are faster than Moore machines because they depend on input values and can change state asynchronously, while Moore machines change state on the clock edge and may be safer to use.

3. Can we convert Mealy machine to Moore machine?
Yes, Mealy machine to a Moore machine, we can divide the state output symbols or values into input symbol paths. When converting a Mealy machine to a Moore machine, we must create a separate state for each new output symbol and divide them according to incoming and outgoing edges.

4. What is a Mealy Machine?
The theory of computation defines a mealy machine as a type of final state machine that determines its output values based on its current state and inputs. It is a machine that allows for at most one transition. A 6-tuple of Q, δ, Ʃ, O, X, and q0 can describe this machine.