3
$\begingroup$

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not included in it?

$\endgroup$
4
$\begingroup$

As per suggestion, I'm posting this as an answer.

Any DFA already is an NFA. Determinizing it will not change the number of states it has, so there are NFA that do not have fewer states than the equivalent minimal DFA.

Maybe also a non-trivial example:

Take the NFA with states $\{q_o, q_1\}$, alphabet $\Sigma = \{a\}$, initial state $q_0$, transitions $\delta(q_0, a) = \{q_0,q_1\}$ and final state $q_1$. It generates the same language as the DFA with the same set of states and alphabet, but transitions $\delta(q_0,a)=q_1$ and $\delta(q_1,a)=q_1$.

$\endgroup$
5
$\begingroup$

The answer to the question depends on its precise meaning.

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always yield a deterministic automaton of that size even when the original automaton is deterministic.

or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

NFA to DFA construction

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)

$\endgroup$
  • 1
    $\begingroup$ I'm not sure I would call the "greedy" power set construction "less formal" than the "naive" power set construction. You can specify both perfectly formally, although the "naive" one is the first solution most people will encounter, of course. $\endgroup$ – G. Bach Dec 4 '13 at 0:08
  • 1
    $\begingroup$ @G.Bach True. I needed some "intuitive terminology" that would separate the two. The first I called formal as that is the one used in "the proof". The second is the one presented in exercise classes, hence practical. No deeper meaning intended. $\endgroup$ – Hendrik Jan Dec 4 '13 at 11:43
-1
$\begingroup$

this is a theoretical question under study/research by some with some related research literature. a general way to study this question is in the form, given particular NFAs, how big are the corresponding (minimized) DFAs? this is sometimes referred to as "blowup" when the corresponding DFA has many more states than the NFA. can something be said about the form of NFAs that do or dont "blow up"? note that NFAs can be given in non-minimized form. there is some complexity theoretical study of this question. see eg:

see eg lemma 1 that shows that there exist NFA-DFA pairs for which "exponential blowup" is guaranteed.

another way to view this is in the opposite direction, that a NFA can be like a compression algorithm for a DFA because for some DFAs an equivalent NFA is much smaller, and the NFA-DFA conversion can be like a decompression algorithm. however searching for the smallest NFA equivalent to a DFA is PSpace complete.

there is also a natural empirical approach to study this question by creating random NFAs and seeing how they "blow up" when converted to DFAs, and finding parameters of the NFA that contribute to that "blow up".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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