Question

Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?

• A. 1
• B. 32
• C. 65
• D. 128

Hint:

For GATE questions: An NFA with $n$ states can result in a DFA with \textbf{at most $2^n$ states}. Any option strictly greater than $2^n$ is impossible.

Answer 1

The Correct Option is C

Step 1: Recall how an NFA is converted into a DFA. 
An NFA with $n$ states can be transformed into an equivalent DFA using the subset construction technique.
In the worst case, this process produces a DFA with up to:

\[ 2^n \]

states.

Step 2: Apply the rule to the given NFA.
Here, the number of states in the NFA is:

\[ n = 6 \]

So, the maximum possible number of states in the equivalent DFA is:

\[ 2^6 = 64 \]

This means the DFA obtained before minimization can have at most 64 states.

Step 3: Consider the effect of DFA minimization.
After minimization, the DFA may have fewer states depending on the language being recognized.
The number of states can range from 1 up to 64, but it can never exceed 64.

Step 4: Check the answer choices.
(A) 1: Possible, for example when the language is either $\Sigma^*$ or the empty set.
(B) 32: Possible, since it is less than 64.
(C) 65: Not possible, because it is greater than the maximum allowed number of states.
(D) 128: Also impossible, but 65 is the smallest such invalid option.

Step 5: Final conclusion.
The number of states in a minimal DFA equivalent to a 6-state NFA cannot be:

\[ \boxed{65} \]