Mealy to Moore Conversion

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?

• 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." ?? – Akash Mahapatra Nov 9 '16 at 8:00

2 Answers

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.