Problem Detail: 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)$.
Asked By : user5507
Answered By : Luke Mathieson
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9998
