1,267 views
0 votes
0 votes

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

 

1 Answer

Best answer
2 votes
2 votes
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

7 votes
7 votes
2 answers
3
debanjan sarkar asked Sep 30, 2016
4,440 views
Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100.A. 102B. 103C. 104D. 105