Any mealy machine can be rebuilt as a moore machine that produces the same output sequence, apart from timing. The problem to solve: a Mealy state can be entered by arrows with different outputs (some x/0, some x/1), but a Moore state needs one fixed output.
The method:
- For each state, look at the outputs on the arrows entering it.
- If they all carry the same output, keep the state and give it that output.
- If they carry different outputs, split the state into one copy per output value. Each copy gets its own fixed output.
- Point each incoming arrow at the copy that matches its output. Give every copy the same outgoing arrows as the original.
The Moore machine usually has more states, and its output appears one clock cycle later, because it now has to move into a state before showing the result. Going the other way, Moore to Mealy, is easier: move each state's output onto the arrows that enter it.