Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite…
2026
Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.
Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to 𝑀 ?
- A.
32
- B.
65
- C.
1
- D.
128
Attempted by 23 students.
Show answer & explanation
Correct answer: B, D
Step 1: Understand the relationship between NFA and DFA states. An NFA with n states can be converted to a DFA with at most 2^n states using the subset construction method.
Step 2: Calculate the maximum number of states. Given n = 6, the maximum number of states in the equivalent DFA is 2^6 = 64.
Step 3: Determine the valid range. The number of states in the minimal DFA equivalent to an NFA with n states must be between 1 and 2^n inclusive.
Step 4: Evaluate the options. Options 32 and 1 are within the range [1, 64]. Options 65 and 128 exceed the maximum limit of 64.
Conclusion: The options that CANNOT be the number of states are 65 and 128.