# Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).

Suppose by regular expression we mean some well-defined finite state machine, I am not familiar with the exact terminology, but let's agree on some class of allowed expressions.

Instead of manually crafting the expression, I want to give it a set of positive and a set of negative examples.

It should then come up with an expression that matches the + ones, rejects the - ones and is minimal in some well-defined sense (number of states in the automata?).

My questions are:

• Has this problem been considered, how can it be defined in some more concrete way and can it be solved efficiently? Can we solve it in polynomial time? Is it NP complete, can we approximate it somehow? For what classes of expressions would it work? I would appreciate any pointer to textbooks, articles or such that discuss this topic.
• Is this related in any way to Kolmogorov complexity?
• Is this related in any way to learning? If the regular expression is consistent with my examples, by virtue of it being minimal, can we say something about its generalization power on yet unseen examples? What criterion for minimality would be more suitable for this? Which one would be more efficient? Does this have any connections with machine learning? Again any pointers would be helpful...

Sorry for the messy question ... Point me in the right direction to figure this out. Thanks !

-
The following page seems very relevant to the learning aspect of the question: people.dsv.su.se/~henke/ML/MERLIN.html –  Tsuyoshi Ito Oct 1 '10 at 21:11
… or maybe not. There seem to be many works on DFA learning anyway. –  Tsuyoshi Ito Oct 1 '10 at 21:38
This question was recently discussed on the community blog. –  Aaron Sterling Aug 26 '11 at 14:43

Yes, it is NP-Hard. Pitt and Warmuth showed that finding the smallest DFA consistent with a given sample cannot be approximated to within $OPT^k$ for any constant $k$, unless $P = NP$.

Regarding the learning question: Kearns and Valiant proved proved that you can encode RSA into a DFA. So, even if the labeled examples come from the uniform distribution, being able to generalize to future examples (also even coming from the uniform distribution) would break RSA. Hence, we think that in the worst case, having labeled examples does not help with learning a DFA (in the PAC model). This is one of the classic cryptographic hardness results for learning.

Both of these issues are intertwined due to what we call the Occam's Razor Theorem. It basically states that if we have a procedure for finding the smallest hypothesis from a given class that's consistent with a sample labeled by a hypothesis from the same class, then we can PAC learn that class. So, given the RSA hardness result, we would expect that finding the smallest consistent DFA would be hard in general!

To add a positive learning result, Angluin showed that you can learn a DFA if you get to make up your own examples, but it requires the additional power being able to ask "is my current hypothesis correct?" This was also a seminal paper in learning.

To answer your other question, this is all indeed related to Kolmogorov complexity, as the learning problem becomes easier when the canonical representation of the target DFA has low compelxity.

-
You beat me with a more recent, stronger result! You should post a better answer later!!1!! –  Tsuyoshi Ito Oct 1 '10 at 21:28
oops sorry! I spent enough time on learning DFA that I had to jump at this :) –  Lev Reyzin Oct 1 '10 at 21:39
Just in case, I was joking in my previous comment. Of course I am happy to see a better answer! –  Tsuyoshi Ito Oct 1 '10 at 21:52
so in other words, the key difference between this problem and regular minimization of DFAs is the presence of negative examples, yes ? –  Suresh Venkat Oct 1 '10 at 22:52
i don't understand. without negative examples, the smallest consistent dfa has just 1 state - the accept state that points to itself... –  Lev Reyzin Oct 1 '10 at 23:10

I answer the learning-related aspects of the question.

This problem seems to be called “DFA learning” in the literature.

Gold [Gol78] showed that it is NP-complete to decide, given k∈ℕ and two finite sets P and N of strings, whether there exists a deterministic finite-state automaton (DFA) with at most k states which accepts every string in P and none of the strings in N. The paper [PH01] seems to discuss problems related to this motivation (there may be many more; this just came up when I tried to find relevant papers with Google).

References

[Gol78] E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh and Vasant Honavar. Learning DFA from simple examples. Machine Learning, 44(1–2):9–35, July 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh-dfa.pdf

-
Thanks for the response, I am looking at the references. Can I vote more than one best answers on this site? :) Again, I am embarrassed that I missed the whole "DFA learning" subfield, even though I studied machine learning for years. –  laszlo kozma Oct 1 '10 at 22:11
@steve: You can accept only one answer, but you can vote up as many answers as you want. –  Jukka Suomela Oct 2 '10 at 9:18
Note that [Gold78] also states that DFA can be learnt in polynomial time (inside the learnability framework of identification in the limit). See also the recent book on Grammatical Inference (pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html) for an overview. –  mgalle Nov 22 '10 at 15:25
@mgalle: Thank you for the additional information. –  Tsuyoshi Ito Nov 22 '10 at 15:58

Throughout this discussion, it has been assumed that finding a minimal regular expression amounts to finding a minimal FSM recognizing the language, but these are two different things. If I remember correctly, a DFA can be minimized in polynomial time, whereas finding a minimal regular expression that represents a given regular language is PSPACE-hard. The latter is one of those results that belong to the folklore of Automata Theory, but whose proof cannot not be found anywhere. I think it is stated as an exercise in Papadimitrou's book.

-
It is correct that the length of regular expression and the number of states in DFA are different objective functions. I answered about the DFA minimization because it has a nicer property (for example, there is a unique DFA with the minimum number of states) and from the way the question was stated I got the impression that the exact objective function was flexible. –  Tsuyoshi Ito Dec 27 '10 at 6:02
Random comment: given the fact that a regular expression of size f(n) can be simulated by an NFA of size O(f(n)), minimizing regular expressions is more like minimizing NFAs, which is obviously harder. –  Hsien-Chih Chang 張顯之 Dec 27 '10 at 6:38
some of this is addressed in the comments to @keith's answer –  Lev Reyzin Dec 27 '10 at 20:23

See also this stack overflow post. The book you're looking for seems to be Introduction to the Theory of Computation by Michael Sipser.

You're asking a couple of different questions, so taking them one at a time:

Is finding a minimal Finite State Machine for a language L NP-complete?


No it isn't. The Stack Overflow post discusses a naive n^2 algorithm for reducing an FSM to its minimal size. (Working backward from stop states, combine states that are "identical" in a precise sense.)

Apparently (I didn't follow the link), there is an n log n algorithm to do this.

I have a training set of strings, how do I find the minimal FSM
that separates the good examples from the bad?


As you phrased it, your training set describes a finite language. Finite languages trivially map to an FSM--create a linear set of states ending in a stop state for each string in your language, no looping required. Then, run the FSM minimization algorithm on the resulting machine.

Is this a good way to build a classifier?


I wouldn't say so. Minimizing the FSM doesn't change its discriminative power--that's sort of the point. The minimal FSM accepts exactly the set of strings as any equivalent non-minimal FSM.

In general, regular expressions are unsuited for classifying novel data. For any finite training set, you will get a RE/FSM that matches only the positive examples in that set, with no ability to generalize to new data. I've never seen an approach that attempts to find an infinite regular language that matches some training corpus.

For machine learning, you'd be looking for something like a naive Bayes classifier, decision tree, neural network, or something more exotic. Russell and Norvig's Artificial Intelligence: A Modern Approach is as good a place as any to find an overview of machine learning techniques (and much, much more.)

-
I don't agree with this answer. If you simply take all positive examples and construct an FSM that accepts only those examples and nothing else, your FSM may be huge. On the other hand, the smallest FSM that accepts all positive examples and no negative examples might be much smaller. –  Jukka Suomela Oct 1 '10 at 21:04
I think the original question made it pretty clear: "an expression that matches the + ones, rejects the - ones and is minimal in some well-defined sense". –  Jukka Suomela Oct 1 '10 at 21:20
@keith the distinction between your answer and mine is quite subtle. when you build your dfa, by creating new states for each string in the sample, you commit yourself to a possibly different language than the one represented by the minimum dfa separating the positive and negative examples. so the algorithm for generating a dfa and then minimizing it unfortunately doesn't do it! –  Lev Reyzin Oct 1 '10 at 22:24
I'm not sure I understand this distinction. If we have a set of positive and negative examples, we have a family of languages that all satisfy these constraints. for each there is a (set of) minimal dfas. As long as I return a DFA that's minimum size, how does it matter which of these languages I pick. –  Suresh Venkat Oct 3 '10 at 19:34
For learning, you want to pick the smallest DFA because it has the best generalization ability. @kieth's procedure won't pick the minimium DFA over all these languages, only the smallest one for the language that's committed to using his procedure. –  Lev Reyzin Oct 3 '10 at 21:19