A regular language \(L\) is accepted by a non-deterministic finite automaton…

GATE · 2025 · CS · Set 1 · Computer Science & IT

1. A.

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

2. B.

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

3. C.

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

4. D.

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

Attempted by 252 students.