<p>I answer the learning-related aspects of the question.</p>
<p>This problem seems to be called “DFA learning” in the literature.</p>
<p>Gold [Gol78] showed that it is NP-complete to decide, given <span class="math-container">$k \in \mathbb{N}$</span> and two finite sets <span class="math-container">$P$</span> and <span class="math-container">$N$</span> of strings, whether there exists a deterministic finite-state automaton (DFA) with at most <span class="math-container">$k$</span> states which accepts every string in <span class="math-container">$P$</span> and none of the strings in <span class="math-container">$N$</span>.  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).</p>
<h5>References</h5>
<p>[Gol78] E Mark Gold.  Complexity of automaton identification from given data.  <em>Information and Control</em>, 37(3):302–320, June 1978.<br />
<a href="https://doi.org/10.1016/S0019-9958(78)90562-4" rel="nofollow noreferrer">https://doi.org/10.1016/S0019-9958(78)90562-4</a></p>
<p>[PH01] Rajesh Parekh and Vasant Honavar.  Learning DFA from simple examples.  <em>Machine Learning</em>, 44(1–2):9–35, July 2001.<br />
<a href="https://doi.org/10.1007/3-540-63577-7_39" rel="nofollow noreferrer">https://doi.org/10.1007/3-540-63577-7_39</a><br />
<a href="http://faculty.ist.psu.edu/vhonavar/Papers/ALT97.ps" rel="nofollow noreferrer">http://faculty.ist.psu.edu/vhonavar/Papers/ALT97.ps</a></p>

CC BY-SA 2.5
2010-11-22T15:25:42.240Z
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 (http://pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html) for an overview.
mgalle
CC BY-SA 2.5
2010-11-22T15:58:10.477Z
@mgalle: Thank you for the additional information.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T22:11:30.997Z
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.
László Kozma
CC BY-SA 2.5
2010-10-02T09:18:49.910Z
@steve: You can *accept* only one answer, but you can *vote up* as many answers as you want.
Jukka Suomela
CC BY-SA 4.0
2010-10-01T21:21:59.840Z
2022-12-21T10:17:47.057Z
2022-12-21T10:17:47.057Z
Tsuyoshi Ito
<p>Yes, it is NP-Hard.  Pitt and Warmuth <a href="https://dl.acm.org/doi/pdf/10.1145/138027.138042" rel="nofollow noreferrer">showed</a> that finding the smallest DFA consistent with a given sample cannot be approximated to within <span class="math-container">$OPT^k$</span> for any constant <span class="math-container">$k$</span>, unless <span class="math-container">$P = NP$</span>.</p>
<p>Regarding the learning question: Kearns and Valiant <a href="http://portal.acm.org/citation.cfm?id=174644.174647" rel="nofollow noreferrer">proved</a> 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.</p>
<p>Both of these issues are intertwined due to what we call the <a href="http://users.soe.ucsc.edu/%7Emanfred/pubs/J9.pdf" rel="nofollow noreferrer">Occam's Razor Theorem</a>.  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!</p>
<p>To add a positive learning result, Angluin <a href="http://portal.acm.org/citation.cfm?id=36889" rel="nofollow noreferrer">showed</a> 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 &quot;is my current hypothesis correct?&quot;  This was also a seminal paper in learning.</p>
<p>To answer your other question, this is all indeed related to Kolmogorov complexity, as the learning problem <a href="http://www.cs.iastate.edu/%7Ehonavar/Papers/icml99.pdf" rel="nofollow noreferrer">becomes easier</a> when the canonical representation of the target DFA has low complexity.</p>

CC BY-SA 2.5
2010-10-01T21:28:29.160Z
You beat me with a more recent, stronger result!  You should post a better answer _later_!!1!!
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T21:39:47.493Z
oops sorry! I spent enough time on learning DFA that I had to jump at this :)
Lev Reyzin
CC BY-SA 2.5
2010-10-01T21:52:15.113Z
Just in case, I was joking in my previous comment.  Of course I am happy to see a better answer!
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T22:24:07.913Z
Thanks for the pointers, this is exactly what I needed. I was not aware that "DFA learning" has received so much attention, although I suspected that the idea should be obvious. EDIT: by obvious "idea" I mean the general problem formulation, not the ways of attacking it, obviously :)
László Kozma
CC BY-SA 2.5
2010-10-01T22:26:53.857Z
yes, lots of the lower hanging fruit is already plucked...
Lev Reyzin
CC BY-SA 2.5
2010-10-01T22:52:00.783Z
so in other words, the key difference between this problem and regular minimization of DFAs is the presence of negative examples, yes ?
Suresh Venkat
CC BY-SA 2.5
2010-10-01T23:10:27.360Z
i don't understand. without negative examples, the smallest consistent dfa has just 1 state - the accept state that points to itself...
Lev Reyzin
CC BY-SA 2.5
2010-10-02T01:45:20.247Z
I think my comment on @kieth's answer explains the difference.
Lev Reyzin
CC BY-SA 2.5
2010-10-03T15:38:06.823Z
@Suresh: Mark Gold showed that not even regular languages can be learned if only positive examples are given.  http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1377#1377
András Salamon
CC BY-SA 2.5
2010-10-03T19:35:15.707Z
@Lev, yes, I just commented on that comment. thanks
Suresh Venkat
CC BY-SA 4.0
2010-10-01T21:21:27.843Z
2022-11-16T12:39:00.733Z
2022-11-16T12:39:00.733Z
Lev Reyzin
<p>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).</p>

<p>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.</p>

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

<p>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?).</p>

<p>My questions are:</p>

<ul>
<li>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.</li>
<li>Is this related in any way to Kolmogorov complexity?</li>
<li>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...</li>
</ul>

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

CC BY-SA 3.0
2011-08-26T14:43:12.383Z
This question was recently [discussed on the community blog](http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/).
Aaron Sterling
CC BY-SA 2.5
2010-10-01T21:11:00.883Z
The following page seems very relevant to the learning aspect of the question: http://people.dsv.su.se/~henke/ML/MERLIN.html
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T21:38:23.607Z
… or maybe not.  There seem to be many works on DFA learning anyway.
Tsuyoshi Ito
<np-hardness><fl.formal-languages><lg.learning><regular-expressions>
Is finding the minimum regular expression an NP-complete problem?
László Kozma
# Is finding the minimum regular expression an NP-complete problem?

(Asked by: username_0 on 2010-10-01)

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 !

**Tags:** np-hardness, fl.formal-languages, lg.learning, regular-expressions

> **Comments:**
> **username_2**: The following page seems very relevant to the learning aspect of the question: http://people.dsv.su.se/~henke/ML/MERLIN.html  
> **username_2**: … or maybe not.  There seem to be many works on DFA learning anyway.  
> **username_1**: This question was recently [discussed on the community blog](http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/).  

---

## 2 answers

### Answer by username_5 on 2010-10-01. Score: 46 | Accepted answer

Yes, it is NP-Hard. Pitt and Warmuth [showed](https://dl.acm.org/doi/pdf/10.1145/138027.138042) 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](http://portal.acm.org/citation.cfm?id=174644.174647) 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](http://users.soe.ucsc.edu/%7Emanfred/pubs/J9.pdf). 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](http://portal.acm.org/citation.cfm?id=36889) 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](http://www.cs.iastate.edu/%7Ehonavar/Papers/icml99.pdf) when the canonical representation of the target DFA has low complexity.

> **Comments:**
> **username_2**: You beat me with a more recent, stronger result!  You should post a better answer _later_!!1!!  
> **username_5**: oops sorry! I spent enough time on learning DFA that I had to jump at this :)  
> **username_2**: Just in case, I was joking in my previous comment.  Of course I am happy to see a better answer!  
> **username_0**: Thanks for the pointers, this is exactly what I needed. I was not aware that "DFA learning" has received so much attention, although I suspected that the idea should be obvious. EDIT: by obvious "idea" I mean the general problem formulation, not the ways of attacking it, obviously :)  
> **username_5**: yes, lots of the lower hanging fruit is already plucked...  
> **username_6**: so in other words, the key difference between this problem and regular minimization of DFAs is the presence of negative examples, yes ?  
> **username_5**: i don't understand. without negative examples, the smallest consistent dfa has just 1 state - the accept state that points to itself...  
> **username_5**: I think my comment on @kieth's answer explains the difference.  
> **username_7**: @Suresh: Mark Gold showed that not even regular languages can be learned if only positive examples are given.  http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1377#1377  
> **username_6**: @Lev, yes, I just commented on that comment. thanks  

---

### Answer by username_2 on 2010-10-01. Score: 14

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>

> **Comments:**
> **username_0**: 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.  
> **username_4**: @steve: You can *accept* only one answer, but you can *vote up* as many answers as you want.  
> **username_3**: 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 (http://pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html) for an overview.  
> **username_2**: @username_3: Thank you for the additional information.  

---

