'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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

Here we will be discussing Mealy to Moore conversation that is commonly used in the Theory of computation.

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

Conversion of Mealy Machine to Moore Machine using Transition table

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

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.

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.