Editing Moore machine (section)

==Relationship with Mealy machines==
As Moore and Mealy machines are both types of finite-state machines, they are equally expressive: either type can be used to parse a [[regular language]].

The difference between Moore machines and [[Mealy machine]]s is that in the latter, the output of a transition is determined by the combination of current [[state (computer science)|state]] and current input (<math>S \times \Sigma</math> as the domain of <math>G</math>), as opposed to just the current state (<math>S</math> as the domain of <math>G</math>). When represented as a [[state diagram]],
* for a Moore machine, each node (state) is labeled with an output value;
* for a Mealy machine, each arc (transition) is labeled with an output value.

Every Moore machine <math>M</math> is equivalent to the Mealy machine with the same states and transitions and the output function <math>G(s, \sigma) = G_M(\delta_M(s, \sigma))</math>, which takes each state-input pair <math>(s, \sigma)</math> and yields <math>G_M(\delta_M(s, \sigma))</math>, where <math>G_M</math> is <math>M</math>'s output function and <math>\delta_M</math> is <math>M</math>'s transition function.

However, not every Mealy machine can be converted to an equivalent Moore machine. Some can be converted only to an ''almost'' equivalent Moore machine, with outputs shifted in time. This is due to the way that state labels are paired with transition labels to form the input/output pairs. Consider a transition <math>s_i\rightarrow s_j</math> from state <math>s_i</math> to state <math>s_j</math>. The input causing the transition <math>s_i\rightarrow s_j</math> labels the edge <math>(s_i, s_j)</math>. The output corresponding to that input, is the label of state <math>s_i</math>.<ref>{{cite book|last1=Lee|first1=Edward Ashford|last2=Seshia|first2=Sanjit Arunkumar|title=Introduction to Embedded Systems|date=2013|publisher=Lulu.com|location=UC Berkeley|isbn=9780557708574|edition=1.08|url=http://leeseshia.org/|accessdate=1 July 2014}}</ref> Notice that this is the source state of the transition. So for each input, the output is already fixed before the input is received, and depends solely on the present state. This is the original definition by E. Moore. It is a common mistake to use the label of state <math>s_j</math> as output for the transition <math>s_i\rightarrow s_j</math>.