How many states of DFA can be converted from an NFA with ‘n’ states?
2021
How many states of DFA can be converted from an NFA with ‘n’ states?
Answer: D. None of the above — An NFA with n states can be converted to an equivalent DFA that has at most 2ⁿ states. Reason: In the subset construction, each DFA state represents a subset…
- A.
n
- B.
n2
- C.
2n
- D.
None of the above
Attempted by 354 students.
Show answer & explanation
Correct answer: D
An NFA with n states can be converted to an equivalent DFA that has at most 2ⁿ states. Reason: In the subset construction, each DFA state represents a subset of the NFA's n states. An n-element set has 2ⁿ possible subsets, so in the worst case the DFA can have up to 2ⁿ states (though often it will have fewer).
A video solution is available for this question — log in and enroll to watch it.
Loading lesson…