14
$\begingroup$

I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to understand. I just want to understand intuitively why NFA minimization is so hard when DFA minimization is not.

$\endgroup$
8
$\begingroup$

For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA.

For NFA the situation is complicated as there is no unique minimal NFA in general.

Here is an example for the finite language $\{ ab, ac, bc, ba, ca, cb\}$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat.

two NFA for the same language

This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity.

$\endgroup$
  • 8
    $\begingroup$ Neither the shortest-path nor the minimum-spanning-tree problem (always) have unique solutions, but they are still efficiently solvable. $\endgroup$ – Raphael Jun 15 '13 at 21:05
1
$\begingroup$

the question does not define "hard" whereas there is a technical sense of the word in TCS. in one sense neither is "hard" (either minimizing DFAs or NFAs) because many algorithms exist for both. however, another angle on this. DFA minimization has runtime $O(ns \log n)$ where s is the number of states ie PTime. NFA minimization has been proven PSpace complete. NFA minimization is not in PTime unless P = PSpace which is widely believed not to be true.

see also this TCS.se question computing the minimal NFA for a DFA

$\endgroup$
  • $\begingroup$ I don't know how to define hard, but I meant that there is no efficient algorithm for solving it. $\endgroup$ – Duncan Jun 16 '13 at 4:24
  • $\begingroup$ @duncan ok, then you used indeed the word in the technical sense. so theres some clarification on technical hardness. in CS, "efficient" is also a technical term taken/defined as the same as PTime. so your question actually is related to an important open question in TCS—it is widely suspected/formulated that NFA minimization (along with all PSpace complete problems) is indeed "hard", ie not in P, but its not proven yet. $\endgroup$ – vzn Jun 16 '13 at 16:37
5
$\begingroup$

You asked about an intuitive take.

In a DFA, any given input prefix can only reach at most one state. One can then merge together pairs of states that are indistinguishable for any suffix. States that can be distinguished by some suffix cannot be merged. This leads to a minimal automaton that is isomorphic to all other minimal automata.

In contrast, if the automaton is nondeterministic then merging suffix-indistinguishable single states is not good enough. For a given input, not all sequences of transitions in an NFA have to result in an accepting state: if just one such sequence exists, that is enough for the NFA to accept. To correctly decide if two states can be merged, one may need to keep track of more information than for a DFA. For instance, suppose there is a word $pq$ in the language, with prefix $p$ that results in some state $P$, yet so that from $P$ there is no accepting state for the suffix $q$. It is possible that there is another state $Q$ that is indistinguishable from $P$ by any suffix other than $q$. In this case one would want to merge $P$ and $Q$. So one needs to extend the notion of when states are indistinguishable, to take into account such "phantom" differences. This essentially requires keeping track of all possible subsets of states.

Going from tracking $n$ states to $2^n$ subsets of states makes dealing with NFA minimization harder in the worst case.

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