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 the NFA to DFA conversion rule.
An NFA with $n$ states can be converted into an equivalent DFA using the subset construction method.
The maximum number of states in the resulting DFA is: \[ 2^n \] Step 2: Apply the rule for the given NFA.
Given number of NFA states: \[ n = 6 \] Maximum possible number of DFA states: \[ 2^6 = 64 \] Thus, the equivalent DFA (before minimization) can have at most 64 states.
Step 3: Consider DFA minimization.
After minimization, the number of states in the DFA can be any number from 1 up to 64, depending on the language recognized.
However, it cannot exceed 64.
Step 4: Analyze the given options.
(A) 1: Possible (for example, if the language is $\Sigma^*$ or $\emptyset$).
(B) 32: Possible, since $32<64$.
(C) 65: Not possible, as it exceeds the maximum limit of $64$.
(D) 128: Also exceeds $64$, but the smallest such impossible option is 65.
Step 5: Conclusion.
The number of states in a minimal DFA equivalent to a 6-state NFA cannot be: \[ \boxed{65} \]