What is a Mealy machine?

Overview

A 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, \Sigma, q_0, \Delta, \delta, \lambda)$:

$Q$ : This is a set of states.

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

$q_0$: This is an initial state.

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

$\delta$: This is a transition function, that is: $Q \times \Sigma \to Q$

$\lambda$: This is an output function, that is: $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:

In the machine above, the transition on input $i$ will give an output $x$ from the state $q_0$. Moreover, from $q_1$ a transition on input $j$ will provide an output $y$.

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

Example

Suppose we have the following Mealy machine:

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

Transitions Explanation

• The first input character is $0$ . Hence, we move to $q_1$ and output a $b$. Our output string is $b$.

• For the next $0$, we move to $q_0$, which outputs an $a$. The output string becomes $ba$.

• The next $1$ gives another $a$. The output string becomes $baa$.

• The last $0$ takes us to $q_1$ and produces a $b$. The final output string is $baab$.

Transition table

The transition table for the above machine will be:

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.