GATE CS 2026 Set 1 Q16 — Regular Expressions and Finite Automata

Using the subset construction method, any nondeterministic finite automaton (NFA) with $n$ states can be converted into an equivalent deterministic finite automaton (DFA) with at most $2^n$ states.

For the given NFA $M$ with $n = 6$ states:

• The maximum number of states in the equivalent DFA is $2^6 = 64$.
• Minimizing this DFA can only reduce (or keep equal) the number of states.
• Therefore, the number of states $k$ in the minimal equivalent DFA must satisfy: $$1 \le k \le 64$$

Let's evaluate the given options based on this range:

• Option A (32): Since $32 \le 64$, this is a possible number of states.
• Option B (65): Since $65 > 64$, this cannot be the number of states.
• Option C (1): Since $1 \le 64$, this is a possible number of states (e.g., if the language accepted is $\Sigma^*$ or $\emptyset$).
• Option D (128): Since $128 > 64$, this cannot be the number of states.

Thus, the options that CANNOT be the number of states are B and D.