# Finding largest regular language containing one set but not another

Say I want to find the largest regular language containing one set of strings but not another set.

So, I've got a programming problem and I've posed it in a good form above. Now what? How do I find a paper that talks about this or find out if it exists?

• Directory of Open Access Journals
• arXiv
• "Mathematics on the Web" index

For searching:

-Google Scholar - Scirus - CiteSeerX

And to my recent surprise some of the articles in "Annals of Math" are available freely in full text.

And if the paper is interesting enough I would pay a fee. Now, why is it so hard for me to find whether or not someone has answered this question? It shouldn't be so tedious. [End Rant]

So, the question. Given two sets $S$ and $T$ of $n$ text strings each that are on average $10^4$ characters long. I need an algorithm that finds the largest regular language containing all of $S$ and none of $T$.

This is interesting because I've already got a use for it. Given a set of example web pages that satisfy a certain property (like a set of Annals of Math pages on which there is a link for Full Text), and a set that don't, it should construct a regular expression that I could use to crawl a site and find all pages that satisfy the property (and list all free Annals papers on a web page). Now I could just construct a simple regex to do that, but then I'd have to do that each time and the regex required may not be as simple as *Full Article*

Oh yeah, the algorithm needs to construct a regular expression to represent the language.

-
This is equivalent to finding the largest regular language not containing $T$. – Enjoys Math Mar 22 '12 at 3:49

Clearly, we must assume that $S \cap T$ is empty.
If $T$ is regular, then obviously $\Sigma^* - T$ is the largest such language.
If $T$ is not regular, then neither is $\Sigma^* - T$, and in that case, there is no such largest language: If $U$ is a regular language between $S$ and $\Sigma^* - T$, and $U$ is not all of $\Sigma^* - T$, then we can always add a missing string from $\Sigma^* - T$ to $U$, and the resulting language will remain regular.
Based on your description of your application, I'm not sure this is the problem you want to solve, though. It sounds like you want to take "good" and "bad" examples of strings and come up with a regex that matches all the goods and none of the bads. A big difficulty with this problem is defining what is considered an acceptable solution. Assuming your example sets are finite, it is easy to create solutions that undergeneralize (just list all the examples in $S$, and allow nothing else), or overgeneralize (allow everything in $\Sigma^* - T$). Neither of these extreme solutions would seem to be useful in practice. You could also specify a condition like "minimize the number of symbols in the regex", though that may turn out to be a very hard problem to solve (I haven't given it much thought).