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

Non-uniqueness of minimal NFA

NFA 2

NFA 1

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.

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).

External links

• A modified C# implementation of Kameda–Weiner (1970)