Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

automata
theoretical cs
fa

What is a Mealy machine?

Zainab Ilyas

Overview

Mealy machine is a finite state machine that has an output value rather than a final state. For a given input, the machine generates a corresponding output. The output of the Mealy machine depends on the present state of the FA as well as the current input symbol.

Unlike other finite automata that determine the acceptance of a particular string in a given language, Mealy machines determine the output against the given input.

Formal theorem

The Mealy machine is a 6 tuple machine (Q,Σ,q0,Δ,δ,λ)(Q, \Sigma, q_0, \Delta, \delta, \lambda):

QQ : This is a set of states.

Σ\Sigma: This is a set of input alphabets.

q0q_0: This is an initial state.

Δ\Delta: This is a set of output states.

δ\delta: This is a transition function, that is: Q×ΣQQ \times \Sigma \to Q

λ\lambda: This is an output function, that is: Q×ΣΔQ \times \Sigma \to \Delta

Note: The output function means that for every transition at a particular state, there is a corresponding output associated with it.

Formation of the machine

The Mealy machine forms an FA of the type:

g ENTRY q0 q0 ENTRY->q0 q1 q1 q0->q1 i / x q1->q0 j / y
An example format of a Mealy machine

In the machine above, the transition on input ii will give an output xx from the state q0q_0. Moreover, from q1q_1 a transition on input jj will provide an output yy.

Note: If the input string is of length nn, the output produced by a Mealy machine will also be of length nn.

Example

Suppose we have the following Mealy machine:

g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / b
An example Mealy machine.

Now, we take an input string in Σ{0,1}\Sigma \{0,1\} and see its output in Σ{a,b}\Sigma \{a,b\}. Let's take x=0010x= 0010.

Transitions Explanation

  • The first input character is 00 . Hence, we move to q1q_1 and output a bb. Our output string is bb.
g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / b
"b" is produced by transition q0 to q1 on "0".
  • For the next 00, we move to q0q_0, which outputs an aa. The output string becomes baba.
g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / b
"a" is produced by transition q1 to q0 on "0".
  • The next 11 gives another aa. The output string becomes baabaa.
g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / b
"a" is produced by transition q0 to q0 on "1".
  • The last 00 takes us to q1q_1 and produces a bb. The final output string is baabbaab.
g ENTRY q0 q0 ENTRY->q0 q0->q0 1 / a q1 q1 q0->q1 0 / b q1->q0 0 / a q1->q1 1 / b
"b" is produced by transition q0 to q1 on "0".

Transition table

The transition table for the above machine will be:

Current State

Destination State for 0

Output at 0

Destination State for 1

Output at 1

q0

q1

b

q0

a

q1

q0

a

q1

b

The Mealy machine is faster than the Moore machine as it is asynchronous to the fluctuations of a clock pulse.

Note: If you want to know about the Moore machine, click here.

RELATED TAGS

automata
theoretical cs
fa
RELATED COURSES

View all Courses

Keep Exploring