Finite State Machine (Transducer): Mealy and Moore

Definition of Mealy and Moore:

Finite State Machine (Transducer): Mealy and Moore

Finite State Machine (FSM) where after processing input it gives some output, corresponding to input is called transducer.

There are two types transducer:

1. Mealy and    2. Moore

Definition of FSM (Transducer)

M = (Q, ∑ , δ, , Г,Δ)

Q is a finite set of initial states

is a finite set of symbols called the input alphabet

${\mathbf{q}}_{\mathbf{0}}$ is the initial state

δ: Transition function

Г: set of output alphabet

Δ: output function

Sometime input alphabet ∑ and output alphabet Г may be same like ∑ = {0, 1} Г = {0, 1}

Or sometime it may differ like ∑ = {0, 1} Г = {a, b}

The only tuple by which we differentiate Moore and Mealy machine is Δ (output function):

• In the Mealy machine, the Δ (output function) depends on the state (present) and input.
• In the Moore machine, the Δ (output function) depends on the only state.

Example of Mealy machine:

∑ = {0, 1}

Transition Function Table:

From the above machine and transition function table, we can see that Δ (output function) depends on the state (present) and input

What is the output of this machine's corresponding input string?

So, Input = 10110 and output is 01011100.

Example of Moore machine:

∑ = {0, 1}

From this machine and transition function it is clear that Δ (output function) depends on only state.

But there is only one problem at Moore machine as we got a 0 at ${\mathbf{q}}_{\mathbf{0}}$ state initially without any input change. This 0 is extra output. We can ignore it or eliminate it by taking an extra state ${\mathbf{q}}_{\mathbf{\lambda }}$ at the initial state and give output λ like

Now check what will be the output of this input string:

So, either we ignore it and write the output 011100 or change the Moore machine by taking an initial state like

Because ω.λ = ω,

What even δ function of ${\mathbf{q}}_{\mathbf{0}}$ just make it same thing at

And make it initial state.

Table of previous Moore machine 1:

Table of previous Moore machine 2:

Note:  So, there is two option either you avoid the extra first output from initial state or add one extra state ${\mathbf{q}}_{\mathbf{d}}$ as the initial state.