354 views

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

a) N x N

b) 2N

c) 2N

d) N!

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

So, anything less than 2N 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 2N

Please suggest the proper explanation for this problem.

+1 vote

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 2N 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$)

1
+1 vote
2
+1 vote