<p>This paper claims to provide minimized NFA in linear time: <a href="https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153" rel="nofollow noreferrer">https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153</a></p>

CC BY-SA 4.0
2020-08-26T09:14:10.220Z
From the abstract: "It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA." It seems that their algorithm only produces a Thompson NFA which is somehow locally minimal among Thompson NFAs. I didn't read the article though.
Ilkka Törmä
CC BY-SA 4.0
2020-08-26T02:17:25.003Z
2020-08-26T02:17:25.003Z
Joshua Wise
<p>This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special cases, less powerful models of NFAs, ...) See below for some references.</p>

<p>T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617–627, 1970.</p>

<p>A. Malcher. Minimizing finite automata is computationally hard. Theoretical Computer Science 327:375-390, 2004.</p>

<p>L. Polák. Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science, 16(5):999–1010, 2005.</p>

<p>G. Gramlich and G. Schnitger. <a href="http://ggramlich.github.com/Publications/approximationSTACS05.pdf">Minimizing NFAs and Regular Expressions.</a> Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 399–411. </p>

<p>H. Gruber and M. Holzer. <a href="http://www.hermann-gruber.com/data/dlt07-final.pdf">Inapproximability of nondeterministic state
and transition complexity assuming P &lt;> NP.</a> Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205–216.</p>

<p>H. Gruber and M. Holzer. <a href="http://www.hermann-gruber.com/data/lata07-final.pdf">Computational complexity of NFA minimization for finite and unary languages.</a> Language and Automata Theory and Applications (LATA 2007), pp. 261–272.</p>

<p>H. Björklund and W. Martens. <a href="http://www8.cs.umu.se/~henrikb/papers/icalp08.pdf">The tractability frontier for NFA minimization.</a> International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5126, pp. 27–38.</p>

<p>J. Geldenhuys, B. van der Merwe, L. van Zijl: <a href="http://www.cs.sun.ac.za/~jaco/wiki/lib/exe/fetch.php?media=research:gvdmvz09.pdf">Reducing Nondeterministic Finite Automata with SAT Solvers.</a> Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, 81–92.</p>

<p><strong>EDIT (June 8, 2015)</strong></p>

<p>Update: The following paper presents a heuristic algorithm for reducing the size of nondeterministic Büchi automata, along with experiments on random automata. As they state in the conclusion, their method applies to NFAs as well: "While we presented our methods in the context of Büchi automata, most of them trivially carry over to the simpler case of automata over finite words."</p>

<p>Richard Mayr, Lorenzo Clemente. <a href="http://www.inf.ed.ac.uk/publications/report/1414.html">Advanced Automata Minimization.</a> POPL 2013. Extended Technical Report EDI-INF-RR-1414.</p>

<p>Their command-line tool <a href="http://languageinclusion.org/doku.php?id=tools">Reduce v1.2</a> can be invoked with the option "-finite" for reducing a given NFA. The implementation is open source and released under the GNU General Public License. </p>

CC BY-SA 3.0
2013-07-15T19:52:34.363Z
Do you know if there are open-source implementations of any of these kicking around?
Joey Eremondi
CC BY-SA 3.0
2015-06-11T03:25:15.383Z
Hi Hermann, thank you very much for all the info!  I know that given an NFA, it is hard to find the smallest equivalent NFA.  But, what about the following: Given a DFA, find the smallest equivalent NFA.  Is this hard?  How hard?
Michael Wehar
CC BY-SA 3.0
2015-06-11T22:52:43.340Z
Sorry, I see now!  The first listed paper addresses this: http://www.springerlink.com/content/y61724u571v487x5/ Also, another paper you listed addresses this for finite regular languages: http://www.hermann-gruber.com/data/lata07-final.pdf Thank you for clarifying this for me!  :)
Michael Wehar
CC BY-SA 3.0
2012-03-26T22:01:22.860Z
2015-06-08T20:36:42.333Z
2015-06-08T20:36:42.333Z
Hermann Gruber
<p>Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient <span class="math-container">$O(n \lg n)$</span> algorithm. Has anyone come up with an algorithm?</p>
<p>A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.</p>
<p>[1] <a href="https://doi.org/10.1007/3-540-54233-7_169" rel="nofollow noreferrer">Minimal NFA problems are hard / Tao Jiang and B. Ravikumar</a></p>
<p>I was reminded of this problem by the following question on the CS.SE site for which a DFA-&gt;NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.</p>
<p>[2] <a href="https://cs.stackexchange.com/questions/130/what-are-the-conditions-for-a-nfa-for-its-equivalent-dfa-to-be-maximal-in-size">What are the conditions for a NFA for its equivalent DFA to be maximal in size?</a></p>

CC BY-SA 3.0
2012-03-23T17:53:34.977Z
The paper you cite shows PSPACE-completeness. In particular, the problem is in PSPACE, which immediately suggests an algorithm. What kind of algorithms are you looking for? Practical and/or heuristic ones? Best-known bounds on the exponent of the running time? Something else?
Joshua Grochow
CC BY-SA 3.0
2012-03-23T17:55:56.767Z
anything other than brute force that takes into account problem structure... it seems an unusual case where an A->B algorithm is very well developed but a B->A algorithm is mostly unstudied.
vzn
CC BY-SA 3.0
2012-03-24T21:11:30.130Z
It's not that unusual, actually.  Before the problem was known to be PSPACE-complete, all attempts to develop efficient algorithms failed, so little was published.  After the problem was known to be PSPACE-complete, nobody tried to develop efficient algorithms, because they knew they would fail, so even less was published.
Jeffε
CC BY-SA 3.0
2012-03-25T00:21:21.407Z
(1) What does “vice versa direction which has been known for decades and is well researched with an efficient O(n lg n) algorithm” mean?  The minimal DFA for an NFA with n states can have size exponential in n, so it would require some nontrivial output encoding.  (2) There is no such thing as “the” minimal NFA for a given regular language.  Compare this with the existence of the minimal DFA.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-26T01:20:51.713Z
JEFFE you have a good point but Im sure there are many Pspace complete problems that still have sophisticated algorithms that take advantage of problem structure besides merely enumerating all possible solutions, true? admit, I cannot think of any off top of my head. maybe you can? guess that would be another interesting question to pose here.
vzn
CC BY-SA 3.0
2012-03-26T01:26:25.063Z
TI good eye, mea culpa, meant O(m lg m) where m=2^n. re (2) yes there is a minimal _size_ NFA in the sense of an NFA such that no NFA has fewer states, but it may not be unique ie maybe multiple NFAs with the same minimal number of states. maybe you can think of an example of this case? (I cannot immediately.)
vzn
CC BY-SA 3.0
2012-03-29T22:39:47.743Z
@vzn: there are two non-isomorphic 2-state NFAs for the language $a^+$
mikero
CC BY-SA 3.0
2012-10-25T15:13:00.643Z
re O(n lg n) for NFA->DFA direction.. 2nd thought, may have been thinking of an experiment that took random NFAs and minimized them. iirc seemed to take O(n lg n) on avg. unpublished work.
vzn
<ds.algorithms><reference-request><fl.formal-languages><automata-theory><optimization>
computing the minimal NFA for a DFA
vzn
# computing the minimal NFA for a DFA

(Asked by: username_0 on 2012-03-23)

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] [Minimal NFA problems are hard / Tao Jiang and B. Ravikumar](https://doi.org/10.1007/3-540-54233-7_169)

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] [What are the conditions for a NFA for its equivalent DFA to be maximal in size?](https://cs.stackexchange.com/questions/130/what-are-the-conditions-for-a-nfa-for-its-equivalent-dfa-to-be-maximal-in-size)

**Tags:** ds.algorithms, reference-request, fl.formal-languages, automata-theory, optimization
> **Comments:**
> **username_1**: The paper you cite shows PSPACE-completeness. In particular, the problem is in PSPACE, which immediately suggests an algorithm. What kind of algorithms are you looking for? Practical and/or heuristic ones? Best-known bounds on the exponent of the running time? Something else?  
> **username_0**: anything other than brute force that takes into account problem structure... it seems an unusual case where an A->B algorithm is very well developed but a B->A algorithm is mostly unstudied.  
> **username_2**: It's not that unusual, actually.  Before the problem was known to be PSPACE-complete, all attempts to develop efficient algorithms failed, so little was published.  After the problem was known to be PSPACE-complete, nobody tried to develop efficient algorithms, because they knew they would fail, so even less was published.  
> **username_3**: (1) What does “vice versa direction which has been known for decades and is well researched with an efficient O(n lg n) algorithm” mean?  The minimal DFA for an NFA with n states can have size exponential in n, so it would require some nontrivial output encoding.  (2) There is no such thing as “the” minimal NFA for a given regular language.  Compare this with the existence of the minimal DFA.  
> **username_0**: JEFFE you have a good point but Im sure there are many Pspace complete problems that still have sophisticated algorithms that take advantage of problem structure besides merely enumerating all possible solutions, true? admit, I cannot think of any off top of my head. maybe you can? guess that would be another interesting question to pose here.  
> **username_0**: TI good eye, mea culpa, meant O(m lg m) where m=2^n. re (2) yes there is a minimal _size_ NFA in the sense of an NFA such that no NFA has fewer states, but it may not be unique ie maybe multiple NFAs with the same minimal number of states. maybe you can think of an example of this case? (I cannot immediately.)  
> **username_4**: @vzn: there are two non-isomorphic 2-state NFAs for the language $a^+$  
> **username_0**: re O(n lg n) for NFA->DFA direction.. 2nd thought, may have been thinking of an experiment that took random NFAs and minimized them. iirc seemed to take O(n lg n) on avg. unpublished work.  

---

## 2 answers

### Answer by username_7 on 2012-03-26. Score: 28 | Accepted answer

This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special cases, less powerful models of NFAs, ...) See below for some references.

T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617–627, 1970.

A. Malcher. Minimizing finite automata is computationally hard. Theoretical Computer Science 327:375-390, 2004.

L. Polák. Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science, 16(5):999–1010, 2005.

G. Gramlich and G. Schnitger. [Minimizing NFAs and Regular Expressions.](http://ggramlich.github.com/Publications/approximationSTACS05.pdf) Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 399–411.

H. Gruber and M. Holzer. [Inapproximability of nondeterministic state
and transition complexity assuming P <> NP.](http://www.hermann-gruber.com/data/dlt07-final.pdf) Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205–216.

H. Gruber and M. Holzer. [Computational complexity of NFA minimization for finite and unary languages.](http://www.hermann-gruber.com/data/lata07-final.pdf) Language and Automata Theory and Applications (LATA 2007), pp. 261–272.

H. Björklund and W. Martens. [The tractability frontier for NFA minimization.](http://www8.cs.umu.se/~henrikb/papers/icalp08.pdf) International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5126, pp. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: [Reducing Nondeterministic Finite Automata with SAT Solvers.](http://www.cs.sun.ac.za/~jaco/wiki/lib/exe/fetch.php?media=research:gvdmvz09.pdf) Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, 81–92.

**EDIT (June 8, 2015)**

Update: The following paper presents a heuristic algorithm for reducing the size of nondeterministic Büchi automata, along with experiments on random automata. As they state in the conclusion, their method applies to NFAs as well: "While we presented our methods in the context of Büchi automata, most of them trivially carry over to the simpler case of automata over finite words."

Richard Mayr, Lorenzo Clemente. [Advanced Automata Minimization.](http://www.inf.ed.ac.uk/publications/report/1414.html) POPL 2013. Extended Technical Report EDI-INF-RR-1414.

Their command-line tool [Reduce v1.2](http://languageinclusion.org/doku.php?id=tools) can be invoked with the option "-finite" for reducing a given NFA. The implementation is open source and released under the GNU General Public License.

> **Comments:**
> **username_8**: Do you know if there are open-source implementations of any of these kicking around?  
> **username_9**: Hi Hermann, thank you very much for all the info!  I know that given an NFA, it is hard to find the smallest equivalent NFA.  But, what about the following: Given a DFA, find the smallest equivalent NFA.  Is this hard?  How hard?  
> **username_9**: Sorry, I see now!  The first listed paper addresses this: http://www.springerlink.com/content/y61724u571v487x5/ Also, another paper you listed addresses this for finite regular languages: http://www.hermann-gruber.com/data/lata07-final.pdf Thank you for clarifying this for me!  :)  

---

### Answer by username_5 on 2020-08-26. Score: 0

This paper claims to provide minimized NFA in linear time: <https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153>

> **Comments:**
> **username_6**: From the abstract: "It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA." It seems that their algorithm only produces a Thompson NFA which is somehow locally minimal among Thompson NFAs. I didn't read the article though.  

---

