HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is DFA a Moore machine or not?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
machinedfanotmoore

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#69418, answer score: 2

Revisions (0)

No revisions yet.