## You are here

HomeMoore machine

## Primary tabs

# Moore machine

A *Moore machine* $M$ is a five-tuple $(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\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)$ is the *output* of $(s,a)$.

A Moore machine can be thought of as a Mealy machine, where that the output function does not depend on the input. Suppose $M=(S,\Sigma,\Delta,\sigma,\lambda)$ is a Moore machine, then $M^{{\prime}}=(S,\Sigma,\Delta,\sigma,\lambda^{{\prime}})$ where $\lambda^{{\prime}}:S\times\Sigma\to\Delta$, given by $\lambda^{{\prime}}(s,a)=\lambda(s)$, is a Mealy machine.

Like a Mealy machine, a Moore machine also has two visual presentations: via a *flow table*, which describes the transitions to the next states and the outputs, or via a *state diagram*.

For example, consider a Moore 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$ | ||
---|---|---|---|

$s$ | $t$ | $s$ | $y$ |

$t$ | $s$ | $t$ | $x$ |

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 column shows the corresponding output symbols.

In addition, one can visualize a Moore machine $M$ by way its state diagram $G_{M}$, which is just a (labeled) directed graph. $G_{M}$ is constructed as follows: the vertices of $G_{M}$ represent the states of $M$, and each is labeled $s|x$, where $s$ is some state of $M$, and $x=\lambda(s)$. An edge from vertices $(s,x)$ to $(t,y)$ is constructed iff there is an input $a$ such that $\sigma(s,a)=t$, in which case the edge is labeled $a$. In the example above, the state diagram $G_{M}$ of $M$ is the following

Let $M$ be a Moore machine. Since $M$ is a special type of a Mealy machine, modification of the transition and output functions of $M$ to handle input words could be defined much the same way as if we were treating $M$ as a Mealy machine. But the downside is is that no output can correspond to the empty input word $\epsilon$. Because the output function $\lambda$ of $M$ is input-independent, a slightly different approach to modification gets rid of the problem:

First, define the extension of the transition function $\sigma$ of $M$ as if it were a Mealy machine:

$\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.$ |

Next, define a function $\beta:S\times\Sigma^{*}\to\Delta$ as follows:

$\beta(s,u):=\lambda(\sigma(s,u)),\mbox{ where }s\in S,u\in\Sigma^{*}.$ |

Call $\beta$ the output function on input *words* for $M$. Notice that $\beta$ is not an extension of $\lambda$, since $\beta$ is *input-dependent*, whereas $\lambda$ is not. Furthermore, $\beta(s,\epsilon)=\lambda(s)$.

The approach above shows that the mechanism of a Moore machine for handling inputs/outputs is different from that of a Mealy machine, even though a Moore machine is really just a Mealy machine.

# References

- 1 S. Ginsburg, An Introduction to Mathematical Machine Theory, Addision-Wesley, (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*, Prentice-Hall, (1966).

## Mathematics Subject Classification

03D05*no label found*68Q45

*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