You are here
HomeMealy machine
Primary tabs
Mealy machine
A Mealy machine $M$ is a fivetuple $(S,\Sigma,\Delta,\sigma,\lambda)$, where
1. 2. $\Sigma$ is an alphabet whose elements are called input symbols,
3. $\Delta$ is an alphabet whose elements are called output symbols,
4. $\sigma:S\times\Sigma\to S$ is a function called the state transition function,
5. $\lambda:S\times\Sigma\to\Delta$ is a function called the output function.
Given an a pair $(s,a)$ of state $s$ and input symbol $a$, the value $\sigma(s,a)$ is the next state of $(s,a)$ and $\lambda(s,a)$ is the output of $(s,a)$.
Since all of the sets involved are finite, there are two ways to visualize a Mealy machine: via a table called the flow table describing the transition and the output functions, or via a directed graph called the state diagram (see details below).
For example, consider a Mealy machine $M$ where $S=\{s,t\}$, $\Sigma=\{a,b\}$, and $\Delta=\{x,y\}$. The state transition function $\sigma$ and the output function $\lambda$ are defined by the following table:
$a$  $b$  $a$  $b$  

$s$  $t$  $s$  $y$  $y$ 
$t$  $s$  $t$  $x$  $y$ 
The first column represents all the states of $M$; the second and third columns are the next states corresponding to the input symbols specified on the top row; and the last two columns show the corresponding output symbols.
In addition, one can visualize a Mealy machine $M$ by way its state diagram $G_{M}$, which is a (labeled) directed graph. $G_{M}$ is constructed as follows: the vertices of $G_{M}$ are states of $M$. An edge from vertices $s$ to $t$ is constructed iff there is an input $a$ such that $\sigma(s,a)=t$. Let $x=\lambda(s,a)$ be the corresponding output. Then the edge from $s$ to $t$ is given a label $ax$. In the example above, the state diagram $G_{M}$ of $M$ is the following
Remark.

A Mealy machine with only one state is called a combinational circuit. It is nothing more than a finite function $\lambda$ from the set of inputs $I$ to the set of outputs $O$.

A Mealy machine can be thought of as a stateoutput machine, if one treats the values of $\sigma$ and $\lambda$ as singleton subsets of $S$ and $\Delta$ respectively. In this regard, a Mealy machine is complete because both $\sigma(s,a)$ and $\lambda(s,a)$ contain at least one element each, for all pairs $(s,a)\in S\times\Sigma$, and sequential because both $\sigma(s,a)$ and $\lambda(s,a)$ contain at most one element each. As such, a Mealy machine is also known as a complete sequential machine.
Viewed as a stateoutput machine, the transition and output functions of a Mealy machine can be extended so input words may be applied to the machine. For the transition function $\sigma$, the extension is defined inductively on the length of input words:
$\sigma(s,\epsilon):=s,\mbox{ and }\sigma(s,ua):=\sigma(\sigma(s,u),a),\mbox{ % where }s\in S,u\in\Sigma^{*},a\in\Sigma.$ 
Like the transition function $\sigma$, the output function $\lambda$ is also extended inductively on the length of input words:
$\lambda(s,ua):=\lambda(\sigma(s,u),a),\mbox{ where }s\in S,u\in\Sigma^{*},a\in\Sigma.$ 
However, unlike $\sigma$, $\lambda$ is not defined for the empty input word $\epsilon$.
References
 1 S. Ginsburg, An Introduction to Mathematical Machine Theory, AddisionWesley, (1962).
 2 M. Arbib, Algebraic Theory of Machines, Languages, and Semigroups, Academic Press, (1968).
 3 J. Hartmanis, R.E. Stearns, Algebraic Structure Theory of Sequential Machines, PrenticeHall, (1966).
Mathematics Subject Classification
03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections