The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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.

asked in Theory of Computation by (157 points) | 354 views

1 Answer

+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 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$)

Hence, Answer is Option B.

answered by Boss (21.8k points)

Related questions

0 votes
1 answer

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

47,139 questions
51,388 answers
66,700 users