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, \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:

An example format of a Mealy machine

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:

An example 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$.
"b" is produced by transition q0 to q1 on "0".
• For the next $0$, we move to $q_0$, which outputs an $a$. The output string becomes $ba$.
"a" is produced by transition q1 to q0 on "0".
• The next $1$ gives another $a$. The output string becomes $baa$.
"a" is produced by transition q0 to q0 on "1".
• The last $0$ takes us to $q_1$ and produces a $b$. The final output string is $baab$.
"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.

RELATED TAGS

automata
theoretical cs
fa

CONTRIBUTOR

Zainab Ilyas
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time