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

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.

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.

• Neither the shortest-path nor the minimum-spanning-tree problem (always) have unique solutions, but they are still efficiently solvable.
– Raphael
Jun 15, 2013 at 21:05

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.

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

• I don't know how to define hard, but I meant that there is no efficient algorithm for solving it. Jun 16, 2013 at 4:24
• @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.
– vzn
Jun 16, 2013 at 16:37

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

• "It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA." "In an NFA, we call a state auxiliary if it has only $\epsilon$-transitions from other states"
– user114966
Aug 26, 2020 at 2:23