Discussion
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?
Answer: D
The false statement is Every DFA that accepts \(L\) has \(\gt 2^{n}\) states.
The subset construction turns an n-state NFA into an equivalent DFA whose states are sets of NFA states, so at most \(2^{n}\) states are needed. A DFA with more than \(2^{n}\) states is never forced, which makes the last statement false.
The other three are true. An NFA with n states is not necessarily minimal, so L may have an NFA with fewer states. A DFA can sometimes be smaller than a given NFA (for instance when the NFA has redundant states). And the subset construction itself proves that a DFA with at most \(2^{n}\) states exists. Only the last statement is false, which is why this multiple-select question has the single key it does.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development