A regular language \(L\) is accepted by a non-deterministic finite automaton…
2025
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
\(≤ 2^n\)states that accepts\(L\). - D.
Every DFA that accepts
\(L\)has\(> 2^n\)states.
Attempted by 171 students.
Show answer & explanation
Correct answer: D
Answer: Only the statement that every DFA accepting the language has more than 2^n states is false.
Statement about existence of an NFA with fewer than n states: Not universally false. Reason: The given NFA might not be minimal, so an equivalent NFA with fewer states can exist, though this is not guaranteed for every language.
Statement about existence of a DFA with fewer than n states: Not universally false. Reason: Some languages accepted by an n-state NFA may admit smaller DFAs, so this statement is possible but not guaranteed.
Statement that there exists a DFA with at most 2^n states: True. Reason: By the subset construction, every n-state NFA can be converted to an equivalent DFA whose states are subsets of the NFA states, giving at most 2^n DFA states.
Statement that every DFA accepting the language has more than 2^n states: False. Reason: The subset construction provides at least one DFA with at most 2^n states, so it cannot be true that every DFA requires more than 2^n states.
Conclusion: The only false statement is the claim that every DFA accepting the language has more than 2^n states.
A video solution is available for this question — log in and enroll to watch it.