NFA minimization

<h2 id="non-uniqueness-of-minimal-nfa">Non-uniqueness of minimal NFA</h2>
<p>Unlike <a href="/facts/Deterministic_finite_automata/9conRLFS">deterministic finite automata</a>, minimal NFAs may not be unique. There may be multiple NFAs of the same size which accept the same <a href="/facts/Regular_language/ahxw67T1">regular language</a>, but for which there is no equivalent NFA or DFA with fewer states.
</p>

<h2 id="external-links">External links</h2>
<ul><li>A modified C# implementation of Kameda-Weiner (1970) <a href="https://github.com/coder0xff/parlex_legacy/blob/132e4a23a599140d22b18ead832626f0c607340f/Automata/NFA.cs#L641">[1]</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Jiang, Tao; Ravikumar, B. (1993), "Minimal NFA Problems are Hard", SIAM Journal on Computing, 22 (6): 1117–1141, doi:10.1137/0222067 <a href="https://doi.org/10.1137/0222067" target="_blank">https://doi.org/10.1137/0222067</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Kameda, Tsunehiko; Weiner, Peter (August 1970). "On the State Minimization of Nondeterministic Finite Automata". IEEE Transactions on Computers. C-19 (7). IEEE: 617–627. doi:10.1109/T-C.1970.222994. S2CID 31188224. Retrieved 2020-05-03. <a href="https://www.researchgate.net/publication/3045459" target="_blank">https://www.researchgate.net/publication/3045459</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

NFA minimization open-in-new

NFA minimization