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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ possible duplicate of NFA with exponential number of states when deteminized $\endgroup$– Wandering LogicCommented Dec 3, 2013 at 18:15
-
$\begingroup$ I read this question and i found some opposing answers. one answer says it's omega(2^Q) and another says it will always have 2^Q states @WanderingLogic $\endgroup$– TomCommented Dec 3, 2013 at 18:30
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
2
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).
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)
answered Dec 3, 2013 at 22:14
-
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. BachCommented Dec 4, 2013 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$ Commented Dec 4, 2013 at 11:43
$\begingroup$
$\endgroup$
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:
- NFA to DFA blowup Calabro
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".
