Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
NFA minimization
open-in-new
<p> In <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a> (a branch of <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>), NFA minimization is the task of transforming a given <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> (NFA) into an equivalent NFA that has a minimum number of states, transitions, or both. While efficient algorithms exist for <a href="/facts/DFA_minimization/qASLWje9">DFA minimization</a>, NFA minimization is <a href="/facts/PSPACE-complete/gkV3vHfX">PSPACE-complete</a>. No efficient (polynomial time) algorithms are known, and under the standard assumption <a href="/facts/P_(complexity)/2TYvck4k">P</a> ≠ <a href="/facts/PSPACE_(complexity)/RIkAClvG">PSPACE</a>, none exist. The most efficient known algorithm is the Kameda‒Weiner algorithm. </p>