A Moore machine $M$ is a five-tuple $(S,\Sigma,\Delta,\sigma,\lambda)$ , where

1. $S$ is an alphabet whose elements are called states,
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.

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'=(S,\Sigma, \Delta,\sigma,\lambda')$ where $\lambda':S\times \Sigma \to \Delta$ , given by $\lambda'(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=\lbrace s,t\rbrace$ , $\Sigma = \lbrace a,b\rbrace$ , and $\Delta = \lbrace x,y\rbrace$ . The state transition function $\sigma$ and the output function $\lambda$ are defined by the following table:

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.

Bibliography

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).