The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
71 views

asked in Theory of Computation by Active (3.6k points) | 71 views

2 Answers

+1 vote

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

answered by Loyal (6.4k points)
edited by
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
0 votes

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 (31.5k points)
edited by
0
Answer is 6
0
i am not getting how the answer is 6?

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,861 questions
47,532 answers
145,984 comments
62,293 users