GATE CS 2025 Set 1 Q.28: Regular Expressions, Finite Automata and Regular Languages

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

$L$ may have an accepting NFA with $< n$ states.

$L$ may have an accepting DFA with $< n$ states.

There exists a DFA with $\le 2^n$ states that accepts $L$ .

Every DFA that accepts $L$ has $> 2^n$ states.

Official answer and solution

Solution

Recall the subset construction upper bound ( $\le 2^n$ DFA states) and note that the given $n$ -state NFA is not necessarily minimal.

(A) True: The given $n$ -state NFA need not be minimal, so a smaller NFA with $< n$ states may accept $L$ .
(B) True: When the given NFA has redundant states (e.g., $L = \Sigma^*$ accepted by an $n$ -state NFA with $n > 1$ ), the minimal DFA has $1 < n$ state.
(C) True: By the Rabin-Scott subset construction, any $n$ -state NFA can be converted into an equivalent DFA with at most $2^n$ states.
(D) FALSE: Since a DFA with $\le 2^n$ states always exists for $L$ , it is false that every DFA accepting $L$ has $> 2^n$ states.

Final answer

Option (D)

Common trap

Misreading the question as asking for TRUE statements instead of FALSE statements.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 28 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.