NFA minimization


In automata theory, NFA minimization is the task of transforming a given nondeterministic finite automaton into an equivalent NFA that has a minimum number of states, transitions, or both. While efficient algorithms exist for DFA minimization, NFA minimization is NP-hard. No efficient algorithms are known. Nonetheless, algorithms exist which implement useful functionality such as Kameda-Weiner. Additional research has been published on the topic.

State minimal NFA

Unlike deterministic finite automata, minimal NFAs may not be unique. There may be multiple NFAs of the same size which accept the same input sequences, but for which there are no NFAs with fewer states which also recognize the same input sequences.