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

Question

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 !

Answer 1

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 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 complexity.

Answer 2

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 \in \mathbb{N}$ 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.
https://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.
https://doi.org/10.1007/3-540-63577-7_39
http://faculty.ist.psu.edu/vhonavar/Papers/ALT97.ps

Answer 3

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.

Answer 4

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.)