in Theory of Computation
1,224 views
0 votes
0 votes

Consider the following DFA D.
The number of states in the minimization of D is __________.

 

in Theory of Computation
1.2k views

4 Comments

3 states
1
1
please send a picture of your answer. (Work out)
0
0
I am getting 5 only?
0
0

MDFA contain 3 states as [q0],[q1,q2,q3],[q4]

1
1

1 Answer

2 votes
2 votes
Best answer
3 STATES

JUST DRAW TABLE AND AS WE CAN SEE ONLY Q4 IS FINAL STATE

 

NOW EQUIVALENCE 0   ------->   [q0 q1 q2 q3]    [q4]

 

equivalence 1 -------------->[q0]  [q1 q2 q3]   [q4]

 

why q1 q2 q3 is in same set because  

on seeing     q1   on a  we get q4

                     q2, q3   on a  also q4     

on seeing     q1 on b  we get  q2

                     q2 on b     q1

                    q3 on  b       q2

  WHICH ARE IN THE SAME SET IN EQUIVALENCE 0 AS FOR  a IT IS Q4 WHICH IS IN ONE SET

FOR B  IT IS Q1,Q2   WHICH IS ALSO IN SAME SET SO ONLY 3 STATES  

IN Q0 ON A IT IS GOING TO Q3 WHICH IS DIFFERENT SET FROM Q4 SO SEPERATE Q0

ON 2ND EQUIVALENCE ALSO GOT SAME RESULT
selected by

Related questions