76 views

asked | 76 views

+1 vote

I think total no. Of states should be 4 ,check it if i done wrong somewhere please help me,

answered by Loyal (9.2k points)
edited
0
here,  ⋋ is denoting empty string. is it true? no where in the question he mentione it.
0
Some books (peter linz) denoted by $\lambda$ or some books denoted by $\epsilon$ ,it is by default.
0
I think u did some mistake

See the question there is a

Transition from q3 to q0 on a

And u didn't show it in your solution
0
Yeah ,u are right ,I will correct that.thanks

Given is NFA first convert it into DFA then convert into Minimal DFA...

By converting NFA to DFA we get 9 ( = 8+1 DS) states and every state is unique therefore DFA is Minimal ===> no.of states in minimal DFA is 9.

the states in DFA are

⋋                           a                         b

*q0                        q1                          q1                      q2

**q1                         -                             -                       q1q3

q2                        q3                           -                        -

**q1q3                     -                           q0q3                q1q2q3

q3                        -                            q0q3                      q2

q0q3                   q1                         q0q1q3                    q2

**q1q2q3               q3                        q0q3                      q1q2q3

**q0q1q3               q1                       q0q1q3                  q1q2q3

add Dead State as one more state and - in the transition leads to Dead state

By state equivalence theorem all are unique states....

* is intial state and ** are final states

note that  ⋋ considered as input symbol not empty string
answered by Boss (49.9k points)
edited
0
0
i am not getting how the answer is 6?

i repeatedly did the question but again and again i am getting 9 only....

1
2