Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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


enter image description here


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.

share|cite|improve this question
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states. – copper.hat Jan 2 '13 at 0:09
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams. – Lucius Jan 2 '13 at 0:10
Or maybe your professor intended for you to have this realisation! – Alex J Best Jan 2 '13 at 0:26
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times $\{2,4,7\}$ is seen less the number of times $\{1,4,7 \}$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum. – copper.hat Jan 2 '13 at 0:32
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point. – Lucius Jan 2 '13 at 0:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.