converting the given NFA to DFA, the transition table is:
|
a |
b |
q0 (initial state) |
q1 |
q3 |
q1 |
q2 |
q2 |
q2 (final) |
q2 |
q2 |
q3 (final) |
q2q4 |
q3 |
q2q4 (=q6,say) (final) |
q2 |
q2q5 |
q2q5 (=q7,say)(final) |
q2q4 |
q2 |
Iteration 1 :- we find the 0-equivalent states:
set 1 = set of non-final states = [q0,q1]
set 2 = set of final states = [q2,q3,q6,q7]
Iteration 2 :- we find the 1-equivalent states: [q0],[q1],[q2,q3,q6,q7]
(q0 and q1 are not 1-equivalent)
Iteration 3 :- we find the 2-equivalent states: [q0],[q1],[q2,q3,q6,q7]
Since no update in the last iteration, we can merge all states in a set into a single state. Hence, states in minimal dfa = no. of sets = 3