Which of the following cannot be the number of states in the minimal DFA equivalent to the NFA of 6 states?
Correct Answer :
65
128
Solution :
The correct options are 65 and 128.
To understand why these cannot be the number of states, let us analyze the relation between the number of states in a Non-Deterministic Finite Automaton (NFA) and its equivalent Minimal Deterministic Finite Automaton (DFA).
Given that the NFA has n = 6 states, the power set construction method allows us to construct an equivalent DFA. Since the set of states of the DFA is a subset of the power set of the NFA states, the maximum number of states in the equivalent DFA (before minimization) is:
Thus, any DFA equivalent to a 6-state NFA can have at most 64 states. Minimizing a DFA can only decrease (or keep equal) the number of states, but it cannot increase them. Therefore, the number of states in the minimal DFA equivalent to a 6-state NFA must be at most 64.
Let us evaluate the given options against this upper limit of 64 states:
1. 1: This is less than or equal to 64, so it is a possible number of states.
2. 32: This is less than or equal to 64, so it is a possible number of states.
3. 65: Since 65 > 64, it is impossible for the minimal DFA to have 65 states.
4. 128: Since 128 > 64, it is impossible for the minimal DFA to have 128 states.
Consequently, the values 65 and 128 cannot be the number of states in the minimal DFA equivalent to the 6-state NFA.
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Mindyard. Perfect for teachers and institutes.
Copyright © 2026 Mindyard. All Rights Reserved.