<p>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.</p>

<h3>Background</h3>

<p>The first and most prominent notion of a Moore machine I've come across is that a Moore machine is a certain kind of <strong>deterministic finite-state transducer</strong>. 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 <em>state output function</em>.</p>

<p>There exists two interpretations of this definition. In the original one presented by Moore, the state output function of the <strong>current</strong> 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 <em>Mealy</em> machines for which no equivalent Moore machines exist. On the positive side, this interpretation admits a (minimal) canonical form.</p>

<p>In the second interpretation, the <strong>successor</strong> 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 <strong>do not</strong> 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 <em>natural</em> choice.</p>

<p>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 <em>state identification</em> (finding the current state in a given Machine by experimentation).</p>

<h3>Questions</h3>

<p>This brings me to my main two <strong>questions</strong>:</p>

<ol>
<li>What are the justifications for using Moore machines as transducers in the first place? The <em>slight</em> 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?</li>
<li>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)?</li>
</ol>

<p>I'm looking forward to your input on this!</p>

CC BY-SA 3.0
2015-05-25T09:02:23.750Z
I am looking forward to the output produced by your question...
J.-E. Pin
CC BY-SA 3.0
2015-05-26T07:32:34.050Z
They're the opposite of "less" machines.  :-)
Greg Kuperberg
CC BY-SA 3.0
2015-05-26T18:15:09.360Z
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.
gardenhead
<automata-theory><fsm>
What exactly are Moore machines?
misberner
# What exactly are Moore machines?

(Asked by: username_0 on 2015-05-23)

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!

**Tags:** automata-theory, fsm

> **Comments:**
> **username_1**: I am looking forward to the output produced by your question...  
> **username_2**: They're the opposite of "less" machines.  :-)  
> **username_3**: 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.  

---

## 0 answers

