NFA minimization

In automata theory (a branch of theoretical computer science), NFA minimization is the task of transforming a given nondeterministic finite automaton (NFA) into an equivalent NFA that has a minimum number of states. While efficient algorithms exist for DFA minimization, NFA minimization is PSPACE-complete.^[1] No efficient (polynomial time) algorithms are known, and under the standard assumption that P ≠ PSPACE, none exist. The most efficient known algorithm is the Kameda–Weiner algorithm.^[2]

Non-uniqueness of minimal NFA

Unlike deterministic finite automata, minimal NFAs need not be unique. There can be several non-isomorphic NFAs with the same (minimum) number of states accepting the same regular language, with no smaller equivalent NFA existing.^[2]

For example, the language ending in $ab$ , denoted by $(a+b)^{*}ab$ over the alphabet $\Sigma =\{a,b\}$ , has no NFA with fewer than 3 states. There is a three-state minimal DFA that deterministically tracks how much of the suffix $ab$ has been seen so far (see picture NFA 1). Furthermore, there is a non-isomorphic minimal NFA for the same language that instead non-deterministically guesses at each $a$ whether it begins the final $ab$ , accepting if that guess is confirmed by the string's end (NFA 2).