Table of contents
1.
Introduction
2.
What is Mealy Machine?
3.
What is Moore Machine?
4.
Conversion of Mealy Machine to Moore Machine using TOC
4.1.
Conversion to a Moore Machine:
5.
Frequently Asked Questions
5.1.
What is the relationship between a Mealy machine and a Moore machine?
5.2.
Which is easier Moore or Mealy?
5.3.
What is Moore and Mealy output?
5.4.
How is a Mealy Machine different from a Moore Machine?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Conversion of Mealy Machine to Moore Machine

Author Malay Gain
1 upvote

Introduction

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(𝜆). 

mealy to moore conversion

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 

Q is a set of finite states of the mealy machine

q0 is the initial state( starting state)

𝛴 is the input alphabet

O is the output alphabet

δ is the transition function (Q*𝛴  → Q)

𝜆 is the output function (Q*𝛴  → O)

What is Mealy Machine

Transition diagram of a Mealy Machine

Also Read, DFA minimization

Here's your problem of the day

Solving this problem will increase your chance to get selected in this company

Skill covered: Programming

How do you create a function in JavaScript?

Choose another skill to practice

What is Moore Machine?

Mealy Machine is a finite state machine whose output depends only on the present state. Moore Machine is defined as (Q, q0, 𝛴, O, δ, 𝜆) where 

Q is a set of finite states of the mealy machine

q0 is the initial state( starting state)

𝛴 is the input alphabet

O is the output alphabet

δ is the transition function (Q*𝛴  → Q)

𝜆 is the output function (Q  → O)

visualization of Moore machine

Transition diagram of a Moore Machine

Check out this article - Moore and Mealy MachineDifference Between Mealy and Moore Machines

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 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

Present State

Input 0

Input 1

Output

q0

q2

q1

a

q1

q3

q2

b

q2

q2

q2

b

q3

q2

q0

b

Also see -  Conversion of Mealy to 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.

Also read - Arden's theorem

Frequently Asked Questions

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.

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.

Also, check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. along with some Contests and Interview Experiences only 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.

Happy learning!

Live masterclass