744 views

1 Answer

0 votes
0 votes

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

Related questions

1 votes
1 votes
0 answers
1
shaurya vardhan asked Oct 24, 2017
902 views
Given : DFA.Minimum number of states required to construct an equivalent NFA isa)2b)3c)4d)6PS: how can we minimize if initial and final states of DFAare not given ?
7 votes
7 votes
2 answers
2
0 votes
0 votes
1 answer
4
Lakshman Bhaiya asked Dec 27, 2018
543 views
Construct a minimal DFA which accepts set of all strings over {a,b}, such that$1)$Second symbol from $RHS$ should be $‘a’$$2)$Third symbol from $RHS$ should be $‘a�...