Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)$.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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).

share|improve this answer
1  
Note that for the effects of proving there is a DFA, any old DFA suffices, as long as it can be proven that it accepts the same language as the NFA. For a proof it doesn't matter is there are extra states, or too many states; what matters it that it is easy to write (and understand) the proof. For practical use such considerations are or central impportance, and complicate things quite a bit. Summarizing, as always theory is easier than practice. –  vonbrand Feb 21 '13 at 3:21

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.