23
$\begingroup$

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

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?

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ 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? $\endgroup$
    – Joshua Grochow
    Commented Mar 23, 2012 at 17:53
  • 8
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Mar 24, 2012 at 21:11
  • 6
    $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 25, 2012 at 0:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Mar 26, 2012 at 1:20
  • 3
    $\begingroup$ @vzn: there are two non-isomorphic 2-state NFAs for the language $a^+$ $\endgroup$
    – mikero
    Commented Mar 29, 2012 at 22:39

2 Answers 2

Reset to default
28
$\begingroup$

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. 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. 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. Language and Automata Theory and Applications (LATA 2007), pp. 261–272.

H. Björklund and W. Martens. The tractability frontier for NFA minimization. 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. 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. POPL 2013. Extended Technical Report EDI-INF-RR-1414.

Their command-line tool Reduce v1.2 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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Do you know if there are open-source implementations of any of these kicking around? $\endgroup$
    – Joey Eremondi
    Commented Jul 15, 2013 at 19:52
  • $\begingroup$ 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? $\endgroup$
    – Michael Wehar
    Commented Jun 11, 2015 at 3:25
  • 1
    $\begingroup$ Sorry, I see now! The first listed paper addresses this: springerlink.com/content/y61724u571v487x5 Also, another paper you listed addresses this for finite regular languages: hermann-gruber.com/data/lata07-final.pdf Thank you for clarifying this for me! :) $\endgroup$
    – Michael Wehar
    Commented Jun 11, 2015 at 22:52
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ilkka Törmä
    Commented Aug 26, 2020 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.