2
$\begingroup$

I went through the rules of Moore and Mealy Machine or FA. I read that both could have one initial state and no final state.

If Moore Machine has one initial state then there is a problem for converting those Mealy Machines into Moore Machines in which inputs coming towards the initial state give different outputs. In this case we will get a Moore Machine which will have many initial states.

For example: if we convert the following Mealy Machine then we will get a Moore Machine with two initial states!

enter image description here

Is there any way to convert such Mealy Machines into single initial state Moore Machines?

$\endgroup$
  • $\begingroup$ Is it really "more than one" initial states? I mean, the state is still $q_0$, it is just that it produces a different output, therefore, it had to be separated. Had it been a whole new initial state, say $q_4$, then it might have violated the rules. $\endgroup$ – Infinity Mar 4 at 10:25
  • $\begingroup$ qo state with 0 output and qo state with 1 output are two different states in Moore Machine. Doesn't matter we call one of them q4. $\endgroup$ – Zeeshan Ahmad Khalil Mar 4 at 10:38
  • $\begingroup$ Well, in that case, if we consider that the states to which we reach after we input 0 and 1 to either of the "q0", will be one and the same. It doesn't matter which initial q0 we choose, we will reach the same states on same inputs. Again, just keeping my point. $\endgroup$ – Infinity Mar 4 at 10:50
4
$\begingroup$

The tutorial that you link to does not explain what "translating" between Mealy and Moore machines actually means, which is however crucial. In every step of its computation, a Mealy machine first reads the next input character, and then produces the next output character while transitioning to the next state. A Moore machine, one the other hand, first produces the next output character and then reads the next input, after which it transitions to the next state.

These two modes of computation are different and hence there is no translation between them that does not alter the semantics of the machine. When you translate from Moore to Mealy, you can build a machine that ignores the next input, produces the next output, and only then takes input and state into account to transition to the next state. The resulting Mealy machine in a sense ignores the next input until it wrote the next output.

When you translate from Mealy to Moore, you have a problem: to compute the next output, you need the next input....which is only available to the machine after producing the next output. What you can do during the translation is however to build a Moore machine that produces its output delayed by one step. This requires you to store the last output in the state component, which blows up the automaton. Whether the resulting Moore machine is good for anything practical is a different question. Even with this semantics-altering translation, there is still the problem that the Moore machine needs to give some initial output, which needs to be defined. This could be an arbitrary one or a designated "no data" output character. This seems to be the choice of your tutorial - rather than having more than one initial state, you declare the one to be initial that is labeled by the output character representing ``nothing''.

Having to choose some initial output shows you that this is no one-to-one translation.

$\endgroup$
  • $\begingroup$ The tutorial is not about "conversion". Its about "Moore and Mealy Machine or FA". $\endgroup$ – Zeeshan Ahmad Khalil Mar 4 at 14:28
  • $\begingroup$ You are saying that "We can't convert Mealy to Moore Machine" ? $\endgroup$ – Zeeshan Ahmad Khalil Mar 4 at 14:30
  • $\begingroup$ @ZeeshanAhmadKhalil 1) I only stated that the tutorial includes a translation, not that it is fully about the translation. 2) You can only translate between a Mealy and a Moore machine while slightly changing the behavior of the machine. Whether you still want to call this a conversion is your decision - I would personally not, because the term "convert" suggests that what you get is semantically the same. $\endgroup$ – DCTLib Mar 5 at 21:59

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.