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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,557 answers

146,278 comments

62,304 users