0
$\begingroup$

In Ullman's Introduction to Automata, Languages and Computation (1979):

We formally denote a finite automaton by a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where $Q$ is a finite set of states, $\Sigma$ is a finite input alphabet, $Q_0$ in $Q$ is the initial state, $F \subseteq Q$ is the set of final states, and $\delta$ is the transition function mapping $Q \times \Sigma$ to $Q$. That is, $\delta(q, a)$ is a state for each state $q$ and input symbol $a$.

A Moore machine is a six-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_o)$, where $Q$, $\Sigma$, $\delta$ and $q_0$ are as in the DFA. $\Delta$ is the output alphabet and $\lambda$ is a mapping from $Q$ to $\Delta$ giving the output associated with each state.

A Mealy machine is also a six-tuple $M = (Q, \Sigma, \Delta, \delta, \lambda, q_o)$, where all is as in the Moore machine, except that $\lambda$ maps $Q \times \Sigma$ to $\Delta$. That is, $\lambda(q, a)$ gives the output associated with the transition from state $q$ on input $a$.

Why do both Moore machines and Mealy machines not have a set of final states, like $F$ in a DFA?

Do DFA's with outputs in general not have a set of final states?

Without a set of final states, how do they decide whether to accept an input string?

Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

Moore and Mealy machines do not exhaust the possible definitions of "finite state machines with outputs". For a more general machine (not necessarily deterministic), see, for example, Finite-state Transducers (FSTs), which usually are defined with final states. But it doesn't really add any additional power to a transducer; you could just as well mark an accepted parse by producing a special "Success!" output symbol at the end of the parse, assuming you had augmented the input with a special "end-of-input" input symbol.

Moore and Mealy machines are intended to model computations which don't have a fixed termination; as long as they continue receiving input, they continue producing output (one output symbol per input symbol). That models a different type of computation than the DFA recogniser (although there are clear relationships). Since the machine cannot "take back" an output symbol already produced, every input -- whether "accepted" or not -- must produce some output. So if you wanted to model a recognizer, you could limit the output alphabet to $0$ and $1$, and define a (finite) input as being "accepted" by the machine if the last symbol output with that input is a $1$.

$\endgroup$
5
  • $\begingroup$ Thanks. (1) For FAs without final sates (e.g. Moore or Mealy), does it make sense to talk about the languages accepted by them? (I guess no.) (2) A different question, for FAs with outputs (e.g. Moore or Mealy), does it make sense to talk about the languages generated/outputted by them? $\endgroup$
    – Tim
    Jun 28, 2020 at 21:23
  • $\begingroup$ 1. Not much. 2. Yes, definitely. $\endgroup$
    – rici
    Jun 28, 2020 at 23:19
  • $\begingroup$ What is the definition of the language generated by a FA with outputs? $\endgroup$
    – Tim
    Jun 28, 2020 at 23:30
  • $\begingroup$ @Tim: an obvious definition would be $\{\beta \mid \exists \alpha\in\Sigma^*: \beta = \lambda^*(q_0, \alpha)\}$, where $\lambda^*(q,\alpha)$ is extended in the obvious way from $\lambda(q,a)$ (that is, the sequence of outputs produced from the input $\alpha \in \Sigma^*$ if the machine is in state $q$). But the wonderful thing about mathematics is that you are free to define anything as you wish (as long as you do so precisely), since definitions are only syntactic sugar intended to make discourse easier to follow. $\endgroup$
    – rici
    Jun 29, 2020 at 2:05
  • $\begingroup$ @Tim: with that definition, it should be immediately obvious that a language generated by a Mealy machine (or equivalently a Moore machine, since there is an equivalence) is a language which could be recognised by some DFA. We can construct the NFA $(Q, \Sigma, \delta', q_0, Q)$ from the Mealy machine, using $\delta(q, a) = \{ q' : \exists b\in\Sigma:\delta(q,a)=q'\and\lambda(q,a)=b\}$ (remembering that every NFA can be turned into an equivalent DFA). Thus, the output languages of Mealy machines are regular (rational). $\endgroup$
    – rici
    Jun 29, 2020 at 2:28

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.