It is false....

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

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.

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

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.

0 votes

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

IT MEANS AT MINIMUM LEVEL BOTH NFA AND DFA EQUAL

BUT AT MAX AROUND 2^n STATES

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,294 answers

182,250 comments

67,741 users