3
$\begingroup$

I understand the difference between DFA (has finite set of accept states, and doesn't have output function, nor output alphabet) and Moore Machine (doesn't have accept states, but has output for every state). But when implementing DFA in programming language, it always generates output. That is, if it last state was accept then it returns TRUE, to indicate that string was in the language. And if the last state was not accept then it returns FALSE. Thus DFA has output function $G\colon Q \to A$, where $Q$ are finite set of states, and $A = \{TRUE, FALSE\}$

So my question is: doesn't that make DFA a Moore Machine?

$\endgroup$
2
$\begingroup$

Imagine a system S1->S2->S3(final).

  • DFA transition rules are (S1,a,S2) and (S2,b,S3).
  • Moore machine rules are (S1,(a,1),S2) and (S2,(b,2),S3).

For the input 'ab',

  • DFA will output 'ab'->TRUE
  • Moore machine will output 'a'->1, 'b'->2.

As you can see, DFA doesn't output at each stage. Independent of the input length, you have one output. However, for the Moore machine, size(input)=size(output). Since the input-output relations differ, you cannot conclude that a DFA is a Moore machine.

$\endgroup$
0
$\begingroup$

A Moore machine outputs a symbol after reading each input symbol. See its formal definition. In contrast, a DFA "outputs" only once, and its output can only be binary.

More generally, different types of mathematical objects are not described by dictionary-style definitions, but rather by formal definitions.

$\endgroup$

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.