Equivalence of NFA and DFA - proof by construction

Question

I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set of subsets of $Q$.

My doubt is when we construct DFA from NFA, all the subsets may not occur in that DFA. So how could we write that the number of states of DFA constructed is $\mathcal{P}(Q)$.

Answer 1

It is true that this construction may result in a DFA with unreachable states. The general construction begins simply by including all possible states, then adding the appropriate transitions, so typically the resulting DFA won't be the smallest DFA that accepts the same language (in terms of the number of states).

An alternative approach is to only add states as you generate the transitions (rather than adding all states at the start). This will give you only reachable states, but even then, this DFA may not be the smallest possible.

Nonetheless both approaches result in a DFA that accepts the same language as the initial NFA.

Thus given an NFA with $q = |Q|$ states, we can always generate a DFA with $2^{q} = |\mathcal{P}(Q)|$ states that accepts the same language as the NFA.

Generating the minimal DFA is a slightly different question (but we know that it will have no more than $|\mathcal{P}(Q)|$ states).

Answer 2

If you indeed follow the construction in the way you describe, then there might be states which are unreachable from the starting state. That's allowed in a DFA, though you can go ahead and remove them without affecting the operation of the automaton.