The GATE Grind

GATE 2025 CS (CS1) – Question 28

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple select

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?

  1. $L$ may have an accepting NFA with $< n$ states.
  2. $L$ may have an accepting DFA with $< n$ states.
  3. There exists a DFA with $\le 2^n$ states that accepts $L$.
  4. Every DFA that accepts $L$ has $> 2^n$ states.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Every DFA that accepts $L$ has $> 2^n$ states.

Explanation

Subset construction gives a DFA with at most 2^n states, so (C) is true. A smaller NFA or DFA may exist, so (A) and (B) are true. (D) is false because a DFA never needs more than 2^n states.