Why is NFA minimization a hard problem when DFA minimization is not?

Question

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.

Answer 1

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.

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.

Answer 2

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.

Answer 3

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

Answer 4

This paper claims to provide minimized NFA in linear time: https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153