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.
More Regular Expressions and Finite Automata questions
GATE 2025 CS (CS1) Q50– Consider the following deterministic finite automaton (DFA) defined over the alphabet, =…
GATE 2025 CS (CS2) Q60– Let = \1,2,3,4\. For x *, let prod(x) be the product of symbols in x modulo 7. We take…
GATE 2024 CS (CS1) Q50– Consider the 5-state DFA M accepting the language L(M)(0+1)* shown in the figure…
GATE 2024 CS (CS1) Q61– Consider the two regular expressions over the alphabet \0,1\: r=0*+1* and s=01*+10*. The…
GATE 2024 CS (CS2) Q22– Which one of the following regular expressions is equivalent to the language accepted by…
GATE 2024 CS (CS2) Q41– Let M be the 5-state NFA with -transitions shown: start state 1 with ε to 2 and ε to 4;…