9
$\begingroup$

Ok, don't be scared by the title - it is not that I don't know the concept of a Moore machine, or basic FSM concepts in general. However, I think that the term "Moore machine", despite being frequently used in some areas, is generally poorly defined. I would be grateful if someone could point me to some (authoritative) source.

Background

The first and most prominent notion of a Moore machine I've come across is that a Moore machine is a certain kind of deterministic finite-state transducer. That is, given an input alphabet $\Sigma$ and an output alphabet $\Omega$, a Moore machine $M$ computes a function $\lambda_M \colon \Sigma^* \to \Omega^*$ such that for each input symbol that is consumed, a single output symbol is produced (this restriction is not always obeyed and, moreover, is not relevant to the question, but I will stick with it for simplicity). Thus, among other things, we have that for all $w \in \Sigma^*$, $|\lambda_M(w)| = |w|$, and in particular $\lambda_M(\varepsilon) = \varepsilon$. A Moore machine $M$ is generally defined as a tuple $M = \langle Q, \Sigma, q_o, \delta, \gamma\rangle$, where $\gamma \colon Q \to \Omega$ is the state output function.

There exists two interpretations of this definition. In the original one presented by Moore, the state output function of the current state determines the output that is emitted when an input symbol is read. Note that in this case, for a given Moore machine $M$, the first symbol of $\lambda_M(w)$, $w \neq \varepsilon$, is necessarily fixed to $\gamma(q_0)$. Note that when relying on this interpretation, there are Mealy machines for which no equivalent Moore machines exist. On the positive side, this interpretation admits a (minimal) canonical form.

In the second interpretation, the successor state determines the output that is emitted when an input symbol is read (i.e., when reading $\sigma\in\Sigma$ in state $q\in Q$, $\gamma(\delta(q, \sigma))$ is emitted). Then, every Mealy machine can be converted into an equivalent Moore machine (with potential blow-up by a factor of $|\Omega|$) and vice versa. However, then Moore machines do not admit a canonical form, due to the degree of freedom introduced by the fact that $\lambda_M$ does not constrain the output of the initial state, i.e., the value for $\gamma(q_0)$. For a more concrete example, consider the transducer with $\Sigma = \{a, b\}$ and $\Omega = \{x, y\}$ that outputs $x$ when reading $a$ and $y$ when reading $b$. The canonical Mealy machine has a single state with two loops with labels $a / x$ and $b / y$. A Moore machine (according to the second interpretation) needs two states, one with output $x$ and one with output $y$. $a$ loops on the $x$-state and $b$ loops on the $y$-state, and the state gets switched on all other inputs. Both states can be chosen as the initial state, and there is no natural choice.

I've also come across a different notion of Moore machines, namely as a generalization of DFA (i.e., where a DFA is a Moore machine with output alphabet $\Omega = \mathbb{B} = \{0, 1\}$ indicating acceptance). In this case, the value $\lambda_M(w)$ of the output function $\lambda_M \colon \Sigma^* \to \Omega$ is a single symbol only, which is determined by $\gamma(\delta(q_0, w))$. While this admits a canonical form, evaluating $\lambda_M(w)$ in general yields significantly less information than in the above case, but also yields information that is not observable in the transducer interpretation (i.e., for $\lambda_M(\varepsilon)$). These aspects are relevant, e.g., in the field of state identification (finding the current state in a given Machine by experimentation).

Questions

This brings me to my main two questions:

  1. What are the justifications for using Moore machines as transducers in the first place? The slight simplicity over Mealy machines comes at a high cost, namely either a reduced expressive power (1st interpretation) or the lack of a canonical form (2nd interpretation), and in either case a potentially increased size compared to a Mealy machine. Am I injust when claiming that for these reasons, the concept of a Moore machine should be avoided altogether in a strictly formal setting?
  2. Is there an established name for the above-mentioned "generalized DFA"? Clearly, the term Moore machine is to confusing, as it is commonly associated with transducers. I've come across TDFA for the ternary case (true, false, unknown/dontcare/maybe/...), but I am looking for a generalization beyond that. Maybe simply GDFA (generalized DFA)?

I'm looking forward to your input on this!

$\endgroup$
  • 1
    $\begingroup$ I am looking forward to the output produced by your question... $\endgroup$ – J.-E. Pin May 25 '15 at 9:02
  • 1
    $\begingroup$ They're the opposite of "less" machines. :-) $\endgroup$ – Greg Kuperberg May 26 '15 at 7:32
  • $\begingroup$ I once read some really good notes on Moore machines, but I can't seem to find them anymore. I'd also like to know the motivation. $\endgroup$ – gardenhead May 26 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.