Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Mealy Machine?
3.
Features of Mealy Machine
4.
What is Moore Machine?
5.
Features of Moore Machine
6.
Differences b/w Mealy and Moore machines
7.
 
8.
Similarities b/w Moore and Mealy machines
9.
Moore Machine to Mealy Machine Conversion
10.
Mealy Machine to Moore Machine Conversion
11.
Frequently Asked Questions
11.1.
Who invented the Moore machine?
11.2.
What is the use of Moore machine?
11.3.
What is DFA and NFA?
11.4.
Is DFA a Moore machine?
11.5.
What is Moore machine output?
11.6.
Where is Mealy machine used?
11.7.
Which machine has 6 tuples?
11.8.
What is a practical example of a Moore machine?
11.9.
Where are Moore machines used?
12.
Conclusion
Last Updated: Mar 27, 2024
Medium

Difference between Mealy Machine and Moore Machine

Introduction

Finite state machines are composed of a finite number of states. These machines respond to some input by changing from one state to another. This change of state is also called transition. 

Difference between Mealy Machine and Moore Machine

Moore and Mealy machines are called Finite Automata with output. This is different from a DFA or NFA (Finite Automata without output) where there is no output (input is either accepted or rejected).

Finite State Machines

Also see, Turing Machine in TOC.

What is Mealy Machine?

In a mealy machine, the output depends on the present state as well as the present input symbol. Here, the output is fixed for every transition (instead of state).

The mealy machine is also defined by 6-tuples (Q, Σ, Δ, δ, λ, q0):

Q = finite set of states
Σ = Input symbol
δ = Transition Function (Q x Σ -> Q)
q0 = Start state
Δ = Output Symbol
λ = Output function (Σ x Q -> Δ)

Example:

Consider the following mealy machine:

Mealy Machine

The transition table for the above mealy machine will be:

Current State

New State

 

0

1

 

State

Output

State

Output

A

B

a

A

b

B

A

b

B

a

The output for the string “1010” in the above machine will be:

States:   A -> A -> B -> B -> A

Output:     b      a      a      b

Note that for an input string of length N, the output string will also have length N.

Also Read - Simplification of CFG

Features of Mealy Machine

A Mealy machine is a type of finite state machine (FSM) used in automata theory and digital electronics. It is characterized by its output being dependent not only on the current state of the machine but also on the input. Here are some features and characteristics of Mealy machines:

  • State Transitions: Like any finite state machine, a Mealy machine consists of a finite number of states. It transitions between these states based on input signals.
  • Inputs: Mealy machines accept inputs from a specified input alphabet. These inputs trigger state transitions and affect the output generation.
  • Outputs: Unlike Moore machines, where outputs depend solely on the current state, in a Mealy machine, outputs are associated with transitions between states and inputs. The output is produced based on both the current state and the input received.
  • Output Function: The output function of a Mealy machine is defined as a mapping from the set of all possible state-input pairs to the set of output symbols.
  • Output Dependency: In a Mealy machine, the output is typically a function of the current state and the input signal that caused the transition to that state. Therefore, the output can change during state transitions triggered by different input symbols.

What is Moore Machine?

A Moore machine is an FSM (Finite State Machine) whose output depends on the present state. It is defined by 6-tuples (Q, Σ, Δ, δ, λ, q0):

Q = finite set of states
Σ = Input symbol
δ = Transition Function (Q x Σ -> Q)
q0 = Start state
Δ = Output Symbol
λ = Output function (Q -> Δ)

The output of a Moore machine in response to the input string a1 a2 a3 a4 ... aN is λ(q0) λ(q1) λ(q2) … λ(qN) where q0 q1 q2 is the sequence of states such that δ(qi-1, ai) = qi

Example:

Consider the following Moore machine

Moore Machine

The transition table for the above machine will look like this:

Current State

Next State

Output

0

1

A

B

A

a

B

B

A

b

 

The output for the string “1010” in the above machine will be:

States:   A -> A -> B -> A -> B

Output:  a      a      b     a      b

Note that for a string of length N, the output string will have length N+1.

Features of Moore Machine

A Moore machine is another type of finite state machine used in automata theory and digital electronics. Unlike the Mealy machine, the output of a Moore machine depends only on the current state and not on the input. Here are some features and characteristics of Moore machines:

  • State Transitions: Similar to other finite state machines, a Moore machine consists of a finite number of states. It transitions between these states based on input signals.
  • Inputs: Moore machines accept inputs from a specified input alphabet. Inputs trigger state transitions, but they do not directly affect the output generation.
  • Outputs: In a Moore machine, outputs are associated solely with states and are independent of the input signals. The output is produced based only on the current state of the machine.
  • Output Function: The output function of a Moore machine is defined as a mapping from the set of all possible states to the set of output symbols. Each state is associated with a specific output symbol.
  • Output Dependency: In a Moore machine, the output is determined solely by the current state of the machine. Therefore, the output remains constant during state transitions triggered by different input symbols.Differences b/w Mealy and Moore machines

Differences b/w Mealy and Moore machines

Mealy Machine

Moore Machine

The output depends both on the present state and the present input. The output depends only on the present state.
It generally has fewer states than Moore's machine. Generally, a Moore machine has more states.
The hardware requirement is comparatively more for circuit implementation. Less hardware requirement for circuit implementation.
They react faster to input. Moore machines react slower to input.
The output generation is asynchronous. The output and state of the change of the device are synchronous with the clock edge.
Comparatively difficult to design. The output and state of the change of the device are synchronous with the clock edge.

 

 

 

 

Similarities b/w Moore and Mealy machines

  1. Both Moore and Mealy machines do not have any final state. 
     
  2. They both produce output in the form of string.
     

Also Read, Moore Machine

Moore Machine to Mealy Machine Conversion

Current State

0

1

Output

 

Next State

Next State

 

A

B

A

a

B

A

B

b

We will use the following steps to convert the Moore machine, to a Mealy machine:-

  • Remove the output column: The output of a Mealy machine depends on the transition, thus the output column has to be removed.
     
  • Add output to transitions: The output of a transition is same as the output of the resultant state in Moore form. 
    In the given table, output of state A is a, so, in the Mealy table, whenever the resultant state is A, the output will be a. Create a new column next to the resultant state, and add the output values.
     

Current State

0

1

 

State

Output

State

Output

A

B

b

A

a

B

A

a

B

b

The number of states in a Mealy machine is either smaller than, or equal to the number of states in an equivalent Moore machine. 

In the next section you will learn how to convert a Mealy machine to a Moore machine.

Also read - Arden's theorem

Mealy Machine to Moore Machine Conversion

Current State

a

b

 

State

Output

State

Output

A

B

a

A

a

B

B

a

C

b

C

B

b

C

a

We will use the following steps to convert the Mealy machine above, to a Moore machine:-

  • First, find the states that have more than 1 output associated with them. 
    In the given table, B is associated with both a and b output, thus 2 new states Ba and Bb have to be created, similarly, C is associated with a and b as well, so, states Ca and Cb have to be created in the Moore equivalent transition table.
     
  • Creating output column: The output of a Moore machine depends on the current state, so it has to be evaluated from the transitions of the Mealy machine. For example, if the state changes from A to B and the output is c, the output of B in Moore machine will be c. 
     

Current State

a

b

Output

 

Next State

Next State

 

A

Ba

A

a

Ba

Ba

Cb

a

Bb

Ba

Cb

b

Cb

Bb

Ca

b

Ca

Bb

Ca

a

If a Mealy machine has ‘m’ states and ‘n’ outputs, then the total number of states in Mealy machine, in a worst case condition will be m*n.

In the next section you will learn about the differences between Moore and Mealy machines.

Frequently Asked Questions

Who invented the Moore machine?

Edward F. Moore invented the Moore machine, a type of finite state machine, in 1956, advancing automata theory.

What is the use of Moore machine?

A Moore machine helps control things by following precise instructions, like traffic lights changing colors predictably to manage traffic flow.

What is DFA and NFA?

DFA (Deterministic Finite Automaton) and NFA (Nondeterministic Finite Automaton) are models in computer science to recognize patterns or languages.

Is DFA a Moore machine?

No, DFA (Deterministic Finite Automaton) is not a Moore machine. DFA has no output associated with its states, while Moore machines do.

What is Moore machine output?

A Moore machine's output is what it displays or produces as a response to an input, like a message or signal.

Where is Mealy machine used?

Mealy machines are used in electronics and computing to make decisions based on input signals and control various devices.

Which machine has 6 tuples?

Both Moore and Mealy machines are defined by 6 tuples. The 6 tuples are, finite set of states, input symbol, transition function, start state, output symbol, output function.

What is a practical example of a Moore machine?

A very simple example of a Moore machine is a doorbell, it has 2 states, idle and ringing. The output only depends on the current state.

Where are Moore machines used?

Moore machines are used for various application such as sequential logic design, implementation of communication protocols, design of embedded systems, industrial automation systems, traffic light control, etc.

Conclusion

In this article, we learned how to convert a DFA into an equivalent DFA having the minimum number of states. If you want to learn more about such topics, you can visit Coding Ninjas Studio.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

You can also consider our Online Coding Courses such as the Machine Learning Course to give your career an edge over others.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass