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

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

a

b

{\displaystyle ab}

, denoted by

(

a

+

b

)

∗

a

b

{\displaystyle (a+b)^{*}ab}

over the alphabet

Σ

=

{

a

,

b

}

{\displaystyle \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

a

b

{\displaystyle 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

{\displaystyle a}

whether it begins the final

a

b

{\displaystyle ab}

, accepting if that guess is confirmed by the string's end (NFA 2).