Consider an $m$ output, $n$ state Mealy machine. How many states does the equivalent Moore machine contain?

The answer is $mn$ but my argument is that the total number of output produced while reading a string of length $n$ ($n$ states) Mealy will produce $m$ outputs ($m$ transitions) but a Moore machine produces a output even in the initial state without any transitions. So to accommodate the first transition of the Mealy machine (the first output of the Mealy) we need another state in the Moore machine. So the answer should be $mn + 1$.

Can anyone tell where am I going wrong?

  • 1
    $\begingroup$ what do you mean by "So to accommodate the first transition of mealy machine ( the first output of mealy ) we need another state in Moore." ?? $\endgroup$ – Akash Mahapatra Nov 9 '16 at 8:00

It is very simple to understand.

The Mealy machine has 'm' outputs that means total 'm' transitions possible.
Number of states are 'n'.

Hence, there are a maximum of m*n transitions possible in total.

All these transitions should be depicted in Moore machine as well, as the power of both are same.


You are right, but you confuse the two possible conversions.

It is asked from Mealy to Moore. The Mealy machine does not have a output at the initial state, as the output depends on input and current state. So there is no additional output to "be accommodated" in the Moore machine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.