53 views
My doubt is it always true that the  number of state in NFA is always less than number of state required in DFA for all language which are regular?
0
It is false....
0
0

In your question, it is mention that "ALWAYS" , that's the reason it is false.

If it is less than or equal to then it will be true.

I hope you  are getting my point.

Make NFA and DFA , and compare them by taking several example , you will definitely get this.

:)

0
@spider1896

Before solving any question, read the question very carefully, then only you will get the clarity of the questions.
0
OK then consider dfa for a number divisible by 2 and nfa for the same number divisible by 2 then in this case dfa will have 2 state but then nfa will have 3 state and then here no of state in dfa will be less than nfa?

Plz clear this doubt of  mine
0

I am hoping that you are asking about " a binary number divisible by 2" .

So, string accepted is :

0

10

110

100

1100

1000

and so on...

So for dfa and nfa ( for both ) it require only 2 states.

suppose q0 and q1 are the two states in minimal dfa and q0 is the final state.

q0 ->0 = q0

q0 ->1 = q1

q1->0 = q0

q1 ->1 = q1

I hope so you will get this, otherwise post your nfa and dfa in the comment section.

There must be mistakes by you when you have solve this question.

MAX NO. OF DFA STATES FOR N NFA STATES IS 2^n

IT MEANS AT MINIMUM LEVEL BOTH NFA AND DFA EQUAL

BUT AT MAX AROUND 2^n STATES
0
OK then consider dfa for a number divisible by 2 and nfa for the same number divisible by 2 then in this case dfa will have 2 state but then nfa will have 3 state and then here no of state in dfa will be less than nfa?

Plz clear this doubt of  mine
0
can you show your nfa having 3 states??
0
@Spider1896 it never happens

+1 vote
1