How many states of DFA can be converted from an NFA with ‘n’ states?
2022
How many states of DFA can be converted from an NFA with ‘n’ states?
- A.
n
- B.
n2
- C.
2n
- D.
None of the above
Attempted by 173 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).