Difference Between Mealy And Moore Machine (Comparison Table)

Before we dive into the basic difference between Mealy Machine and Moore Machine, let's first understand finite state machines. Because both Mealy and Moore are finite state machines in the theory of computation. 

The input combinational circuit in synchronous sequential circuits is made up of a series of logic gates, with flip flops serving as memory elements. The synchronous sequence machine is described by the finite state machine (FSM), which is an abstract model. In a sequential circuit, the output is determined by the current input as well as previous history, necessitating an endless storage capacity.

Finite state machines are utilized because machines with infinite storage capacity are impossible to implement. Finite state machines are sequential circuits with a finite number of ways in which their past history might affect their future behavior.

Machines with a finite number of states are known as finite state machines. There are a limited number of memory devices in any finite-state system. We can construct a periodic sequence of fewer than or equal to n-states using an n-state machine.

There are two types of finite state machines (FSM) and the major difference between the two is in the generation of output. These types are: 

1. Moore Machine
2. Mealy Machine

The fundamental difference between the Mealy and Moore machines is based on whether the dependency of output is on the current state and input.

The current output of the Moore machine is solely determined by its current state. The current output of the Mealy machine is determined by the present state and present external inputs. Both Moore and Mealy machines are quite complex machines.

Moore and mealy machines are generators. Moore and Mealy machines have no knowledge of a final state because they aren't used to recognize languages. Moore and Mealy machines are finite-state deterministic devices.

What is a Moore Machine?

When each state of a finite state machine has an output symbol, the automata is known as a Moore machine. It generates an equivalent string for each input string.

It includes all string transitions for the given alphabet. The current state and current input symbol determine the next state. After the entire input sequence has been applied, the output is evaluated.

The output and state of the device change is synchronous with the clock edge. Moore machine generates the output associated with the initial state by reading no input symbol.

The output of a Moore circuit is solely determined by the current state of the memory elements. If the length of the input string is n, the length of the string produced by this machine will be (n+1).

Block diagram of Moore Machine

Moore Machines Characteristics

M = (Q, Ʃ, ∆, δ, Λ, q0) is a 6 tuple notation
Where Q is the set of finite states.
Ʃ is an input alphabet containing a finite number of input symbols 
∆ is an output alphabet that contains a finite number of the output string
δ is a transition function of input δ: Q x  Ʃ  --> Q 
Λ is an output function: Λ: Q  -->  ∆ (output associated with state)
q0 is an initial state, q0 ∈ Q

For example: 

Construct a Moore machine that takes a set of all strings over {a, b} as input and prints '1' as output for every occurrence of 'ab' as a substring. 

Ans: 

Ʃ(input alphabet) = (a, b)                                                                                                  Input: abaababaa

∆(output alphabet) = (0, 1)                                                                                               Output: 0010010100

Q(finite states) = (A, B, C)

What is a 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. It creates an equivalent output string for each input letter/string.

If the length of the input string is n, the length of the Moore machine's output string is also n. The value of the output function becomes a function of transitions and changes when the input logic is completed in the current state.

On the current clock, the asynchronous output generation changes its state to synchronous. The Mealy circuit's output values are influenced by both the current state output of memory elements and external inputs.

In this type of circuit, Mealy machines respond to inputs more quickly. They all seem to react in the same clock cycle. It takes care of all string transitions across a specified alphabet. A Mealy machine is not a counter.

Block diagram of Mealy Machine

Mealy Machines Characteristics

M = (Q, Ʃ, ∆, δ, Λ, q0) is a 6 tuple notation

Where Q is the set of finite states.

Ʃ is an input alphabet containing a finite number of input symbols. 

∆ is an output alphabet which contains a finite number of output string

δ is a transition function δ: Q x  Ʃ  -->  Q

Λ is an output function: Λ: Q x  Ʃ   -->  ∆(output associated with state and input)

q₀ is an initial state, q₀ ∈ Q.

For example: 

Construct a mealy machine that generates 2's complement of a binary number.

Ans:

The following machine reads input from right to left and produces output from right to left

Ʃ(input alphabet) = (0, 1)                                                             Input = 1100              Output = 0100

∆(output alphabet) = (0, 1)                                                          Read I/p = 0011        Produced O/p = 0100

Q(finite states) = (A, B)                         

Every Moore machine can be converted to a Mealy machine and every Mealy machine can be converted to a Moore machine. Moore machine and Mealy machine are equivalent.

Difference between Mealy Machine & Moore Machine

The following are the key differences between the Mealy machine Moore machine:

Well, now that we understood the similarities and differences between the two, both machines are equivalent since they can be converted to each other. A Mealy machine requires fewer states to implement a function. On the other hand, a Moore machine will have more states to implement the same function.

Frequently Asked Questions

1. How are output values determined in Mealy and Moore machines?

In Mealy machine, the output value depends on both, the current state and the input state. In Moore machine, the output value only depends on the current state. 

2. What are some examples of Mealy and Moore machines?

Examples of Moore Machine: Counter, Digital clocks, state machines controlling a video game character's behavior, etc. 

Examples of Mealy Machine: Traffic lights, microwaves, vending machines, etc. 

3. Mealy vs Moore Machine - which is better?

There is no fixed answer to this question because which machine is better depends on the purpose i.e. the specific application of the machine. In applications where the output has to be updated immediately after changing the input, a mealy machine works better. In applications where the output does not have to update immediately after changing the input, or when the output is independent of input, Moore machines are better. 

4. What's the key difference between Mealy and Moore machine?

The key difference between Mealy and Moore machines is in the way the output is generated. Mealy machines depend on the current state and the input state to generate output. Moore machine only depends on the current state to generate output. Apart from this, a Moore machine is simpler than a Mealy machine but takes longer to react to changes. 

You might also be interested in reading:

1. What is The Difference Between Linear And Non Linear Data Structure?
2. Difference Between Paging And Segmentation Explained!
3. Difference between Mutex and Semaphore in Operating System Explained!
4. What Are The Types of Operating System?