GATE 2025 CS1 Q.28: solution and answer

Official answer: DSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

1. The question asks which statements are FALSE. The NFA has $n$ states, but nothing says $n$ is the smallest number of states any NFA for $L$ needs.

2. (A) Take $L={\Sigma }^{\ast }$. It is accepted by an $n$-state NFA for any $n\ge 2$ (add extra states that do not change the language). A 1-state NFA also accepts it, and $1<n$. So $L$ may have an NFA with fewer than $n$ states, and (A) is TRUE.

3. (B) In the same example, a 1-state DFA with a single accepting state looping on every symbol accepts ${\Sigma }^{\ast }$, and $1<n$. So $L$ may have a DFA with fewer than $n$ states, and (B) is TRUE.

4. (C) The subset construction turns an $n$-state NFA into a DFA whose states are subsets of the NFA's states. There are at most $2^n$ subsets, so a DFA with $\le 2^n$ states accepting $L$ exists. (C) is TRUE.

5. (D) The claim is that every DFA for $L$ has more than $2^n$ states. By (C), some DFA for $L$ has at most $2^n$ states, so the claim fails. (D) is FALSE.

6. Only (D) is a false statement, so the answer is (D).