GATE 2026 CS1 Q.26: solution and answer

Official answer: B, DSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

1. Subset construction turns an NFA with $n$ states into a DFA whose states are subsets of the NFA's states, so there are at most $2^n$ of them.

2. For $n=6$ this gives at most $2^6=64$ states. The empty subset (the dead state) is already counted in the 64.

3. The minimal DFA is never larger than the DFA from the subset construction, so it has at most $64$ states. Hence $65$ (option B) and $128$ (option D) are impossible.

4. Option C is possible. Take a 6-state NFA for ${\Sigma }^{\ast }$: its start state is accepting and loops on every symbol, and the other five states are unreachable. The minimal DFA for ${\Sigma }^{\ast }$ has one state.

5. Option A is possible. Let $L$ be the set of strings over $\{a,b\}$ whose 5th symbol from the end is $a$. A 6-state NFA accepts $L$. State $q_0$ loops on $a$ and $b$ and moves to $q_1$ on $a$. States $q_1,\dots ,q_4$ each move to the next state on both $a$ and $b$. State $q_5$ is accepting. The minimal DFA for $L$ must remember the last 5 symbols, so it has exactly $2^5=32$ states.

6. So 32 and 1 can occur, and 65 and 128 cannot. The options that CANNOT be the size of the minimal DFA are B and D.