Moore machine

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 machines is that in the latter, the output of a transition is determined by the combination of current state and current input (${\displaystyle S\times \Sigma }$ as the domain of ${\displaystyle G}$), as opposed to just the current state (${\displaystyle S}$ as the domain of ${\displaystyle G}$). When represented as a state diagram,


Every Moore machine ${\displaystyle M}$ is equivalent to the Mealy machine with the same states and transitions and the output function ${\displaystyle G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))}$, which takes each state-input pair ${\displaystyle (s,\sigma )}$ and yields ${\displaystyle G_{M}(\delta _{M}(s,\sigma ))}$, where ${\displaystyle G_{M}}$ is ${\displaystyle M}$'s output function and ${\displaystyle \delta _{M}}$ is ${\displaystyle M}$'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 ${\displaystyle s_{i}\rightarrow s_{j}}$ from state ${\displaystyle s_{i}}$ to state ${\displaystyle s_{j}}$. The input causing the transition ${\displaystyle s_{i}\rightarrow s_{j}}$ labels the edge ${\displaystyle (s_{i},s_{j})}$. The output corresponding to that input, is the label of state ${\displaystyle s_{i}}$.^[2] 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 ${\displaystyle s_{j}}$ as output for the transition ${\displaystyle s_{i}\rightarrow s_{j}}$.

Moore-and-Mealy-Machine