Mealy Machine

In this class, We discuss the Mealy Machine.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of the Moore machine. Click Here.

Mealy Machine: The mealy machine is a finite state machine with an output value on each transition.

The below diagram shows the simple mealy machine.

Mealy Machine 1.1

We have two states, A and B.

On state A, if we see the input symbol a, we move to state A and display output 1.

We define output on the transition. Not on the state.

On state A if we see the input symbol b, we move to state B and display output 0.

The below diagram shows the transition table for the mealy machine.

Mealy Machine 1.2

Take an input string abbba.

Suppose we process the input string abbba. The mealy machine will display the output 10001.

We start from the initial state A, take the first input symbol a, move to state A, and display 1.

Take the next input symbol, b and move to state B and display 0.

Similarly, we process the remaining input symbols.

Example: write a mealy machine to convert a binary number to its 2’s complement.

Logic: Take a binary number 10100.

The 2’s complement of 10100 is 01100.

We move from right to left on the binary number.

We keep the binary values the same until we find the first 1.

After finding the first one, we change the bits from 0 to 1 and 1 to 0.

The below diagram shows the mealy machine to convert binary to its 2’s complement form.

Mealy Machine 1.3

On state q0, if we find the input symbol zero, we move to state q0 and display zero.

On state q0, if we find the input symbol one, we move to state q1 and display 1.

We are moving to state q1 when we find the first input symbol 1.

We use the state q1 to change the bits 1 to 0 and 0 to 1.

On state q1, if we see input symbol 0, we display 1.

Similarly, for input symbol one, we display 0.

We represent the mealy machine using six tuples.

{Q,q0, Σ, O,δ,λ}

Q Finite set of states.

q0 Initial state.

Σ Finite set of input symbols.

O output alphabet.

δ Transition function Q X Σ – Q

λ Output Function Q X Σ – O