NFA minimization
From Wikipedia, the free encyclopedia
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, transitions, or both. 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 may not be unique. There may be multiple NFAs with the same number of states that accept the same regular language, but for which there is no equivalent NFA or DFA with fewer states.[example needed]
