[Math] My Moore and Mealy machines look the same. Why

automata

For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with different labels.

Example

  • Input alphabet: {0, 1, …, 9}
  • Output alphabet: {0, 1}
  • Function: Output 1 if the current number is divisible by 3, else output 0.

Moore

enter image description here

Mealy

enter image description here

You see, all I did for creating the Mealy machine was moving the output from the nodes to the connections. Which would make it quite trivial to convert an arbitary Moore machine to a Mealy machine.

Possible sources of my confusion:

  1. My understanding of the differences between the two types is fundamentally flawed.
  2. The conversion Moore => Mealy is in fact trivial.
  3. This example is a special case where the Mealy and Moore machines look the same.
  4. There is a simpler Mealy machine than the one I built here.
  5. My Moore machine is not a valid Moore machine. / My Mealy machine is not a valid Mealy machine. (see 4)

I tried to start from scratch building the Mealy machine, but as I found Moore much easier to build I am always biased towards the Moore solution.

Best Answer

The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$ G:S\rightarrow \Lambda $$ where $S$ is the set of states and $\Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$ G:S\times\Sigma\rightarrow \Lambda $$ where $S$ is the set of states, $\Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $\Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.

We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:S\rightarrow \Lambda$ to a function $G_2:S\times\Sigma\rightarrow \Lambda$ so that for any input symbol $a\in \Sigma$ and state $s\in S$, $$ G_2(s,a)=G_1(s) $$ So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.

In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.

For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.

Related Question