The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

Q.) Given an arbitrary DFA with 2^{N }states, what will be the number of states of the corresponding NFA?

a) N x N

b) 2^{N}

c) 2N

d) N!

**Now, as we know that -> no. of states in minimal DFA >= no. of states in NFA.**

So, anything less than 2^{N} shall satisfy the answer, right? So, according to me a, b, c, all three can be the answer but the answer which I found in the source is option (b) i.e 2^{N}.

Please suggest the proper explanation for this problem.

+1 vote

**Answer : B**

Number of States in Minimal NFA $\leq$ Number of States in Minimal DFA

Here, the DFA has $2^N$ states (He hasn't given that the DFA is Minimal DFA)... hence, "Anything less than 2^{N} **could/couldn't** satisfy the answer....But anything more than or equal to $2^N$ will definitely satisfy the answer. (Because He is Not interested in Minimal DFA or Minimal NFA)"

Option B is the best suitable answer as We can guarantee that **some Equivalent NFA**(He hasn't asked for Minimal NFA) will have $2^N$ states.

Let's eliminate Options :

1. Let the language be $\Sigma^*$..Hence, Some DFA(minimal DFA) will be there with only $1$ state. Hence, Let the arbitrary DFA given in the Question have $1$ State. Hence, $N = 0$

We know that All the NFAs accepting $\Sigma^*$ will have at least One state.

Hence, Option $A,C$ are eliminated.

2. Let the language be $L2$ = $\Sigma^* - \left \{ \in \right \}$ .. Then we know every DFA that will accept this language will have at least $2$ states. Let the Arbitrary DFA have Two states (minimal DFA)... then $N = 1$

Furthermore, we know every NFA that will accept this language $L2$ will have at least $2$ states. Hence, Option $D$ is eliminated (Because $N = 1$)

**Hence, Answer is Option B.**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,164 questions

43,621 answers

124,006 comments

42,880 users