DFA minimization: where did I go wrong

1 reply · 2K views · last reply
gratusri
Messages
1
Reaction score
0
Thread moved from the technical math forums to the schoolwork forums
so this is the question , I have to minimize this DFA

State diagram of a DFA with states q0 to q5, start state q0, accepting states q3 and q5. Transitions: q0 on 0 to q1, q0 on 1 to q3, q1 on 0 to q0, q1 on 1 to q3, q2 on 0 to q1, q2 on 1 to q4, q4 on 0,1 to q3, q3 on 0,1 to q5, q5 on 0,1 to q5.


this is How I did it

Handwritten DFA minimization work: a transition table with states q0, q1, q2, q3, q4, q5 on inputs 0 and 1, followed by equivalence classes 0 and 1 and a final table with the minimized DFA diagram below.


but when I checked for answers , this is what it was,
State diagram of a DFA with states q0, q1 and q3, start state q0 and accepting state q3 (double circle). q0 goes to q1 on 0 and to q3 on 1; q1 goes to q0 on 0 and to q3 on 1; q3 loops to itself on 0,1.
can someone please explain to me what mistake I made? I have been wondering about this for past 2 days
 
gratusri said:
can someone please explain to me what mistake I made?
No idea but your answer is not even a single DFA. The book answer is clearly correct and can be determined quickly by inspection*: are you sure you are expected to use an eigenvalue method to get to the answer?

*Note that there are no paths to q2 and q4 and q3 accepts so the path to q5 is irrelevant