Question

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?

• A. \( L \) may have an accepting NFA with \(< n\) states.
• B. \( L \) may have an accepting DFA with \(< n\) states.
• C. There exists a DFA with \( \leq 2^n \) states that accepts \(L\).
• D. Every DFA that accepts \(L\) has \(>2^n \) states.

Hint:

The conversion from NFA to DFA can cause an exponential increase in the number of states. However, some DFA constructions can still have fewer states depending on the language.

Answer 1

The Correct Option is B

Option (A): This is true. An NFA can potentially accept a language using fewer states due to non-determinism, but for DFA equivalence, the number of states could be larger.

Option (B): This is false. A DFA may require more states than an NFA to accept the same language. For any language accepted by an NFA with \( n \) states, the equivalent DFA may have up to \( 2^n \) states, but it cannot have fewer states.

Option (C): This is true. There is always a DFA with \( 2^n \) states for any language accepted by an NFA with \( n \) states (since \( NFA \to DFA \) conversion can potentially lead to exponential state growth).

Option (D): This is false. A DFA does not always need more than \( 2^n \) states. It is possible for the DFA to have fewer states than \( 2^n \), depending on the language.

Thus, the correct answer is \( \boxed{D} \).