patternMinor
Mealy to Moore Conversion
Viewed 0 times
conversionmooremealy
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#65781, answer score: 3
Revisions (0)
No revisions yet.