GATE CS 2025 Set 1 — Question 28

Analysis of the statements regarding a regular language $L$ accepted by an $n$-state NFA: This is true. If the given $n$-state NFA is not the minimal NFA for the language $L$, then there exists a smaller NFA that accepts the same language. This is true. For certain languages, the minimal DFA can have fewer states than a given non-minimal NFA. For example, an NFA with 2 states for the language $\Sigma^*$ can be simplified to a DFA with only 1 state. This is true. According to the powerset construction (or subset construction) algorithm, any NFA with $n$ states can be converted into an equivalent DFA with at most $2^n$ states. This is false. It directly contradicts statement (C). Since we know there exists at least one DFA (from the subset construction) with $\leq 2^n$ states, it is impossible for every DFA to have more than $2^n$ states.Since the question asks for the FALSE statement(s), only (D) is the correct choice.