NFA to Minimal DFA State Bound

The conversion from a Nondeterministic Finite Automaton (NFA) to an equivalent Deterministic Finite Automaton (DFA) is often done using the subset construction method.

For an NFA with $n$ states, the resulting DFA generated by the subset construction can have at most $2^n$ states. Each state in the DFA corresponds to a unique subset of the NFA's states.

Maximum States Calculation

Given an NFA ($M$) with $n=6$ states.

The theoretical upper limit on the number of states for the equivalent DFA, derived from the subset construction, is:

$ \text{Max DFA States} \le 2^n $

Plugging in $n=6$:

$ \text{Max DFA States} \le 2^6 = 64 $

This means the minimal DFA equivalent to the 6-state NFA cannot have more than 64 states.

Evaluating Options Against the Bound

We check which options exceed the calculated maximum of 64 states:

• Option 1 (32 states): Since $32 \le 64$, this is a possible number of states for the minimal DFA.
• Option 2 (65 states): Since $65 > 64$, this number of states is impossible for the minimal DFA.
• Option 3 (1 state): Since $1 \le 64$, this is a possible number of states (e.g., for trivial NFAs).
• Option 4 (128 states): Since $128 > 64$, this number of states is impossible for the minimal DFA.

Identifying Impossible State Counts

The options that represent a number of states greater than the maximum possible bound ($2^6 = 64$) are the ones that CANNOT be the number of states in the minimal DFA.

Therefore, the impossible numbers of states are 65 and 128.