The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
44 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?
asked in Theory of Computation by (339 points) | 44 views
0
It is false....
0
Pls support your answer through example
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.

1 Answer

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
answered by Active (4.9k points)
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

Related questions

0 votes
1 answer
7
asked Jun 6 in Theory of Computation by Shivani gaikawad Junior (743 points) | 65 views


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

44,081 questions
49,595 answers
162,959 comments
65,791 users