patternMinor
Is DFA a Moore machine or not?
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?
So my question is: doesn't that make DFA a Moore Machine?
Solution
Imagine a system
For the input
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.
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.