<p>The special case of having exactly one word in $A$ and one word in $B$ has <a href="https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22494#22494">been mentioned here before</a>.</p>

<p>This is called the "The Separating Words Problem". The slides by Shallit pretty much cover all that is known about the problem (see <a href="https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf" rel="nofollow noreferrer">slides1</a> and <a href="https://cs.uwaterloo.ca/~shallit/Talks/bc4.pdf" rel="nofollow noreferrer">slides2</a>).</p>

CC BY-SA 3.0
2015-04-20T01:44:10.547Z
If you're interested in finding the smallest DFA for the special case see: http://cstheory.stackexchange.com/questions/29119/finding-the-smallest-dfa-that-separates-two-words-without-using-brute-force-sear
Michael Wehar
CC BY-SA 3.0
2015-04-15T09:45:46.640Z
2015-04-15T11:14:11.770Z
2017-04-13T12:32:28.167Z
R B
<p>The question you are asking is known as the separation problem for languages: Given two languages $K$ and $L$, is there a third language $M$ (a separator) that separates them, i.e. $K \subseteq M$ and $M \cap L = \emptyset$.</p>

<p>You are interested in the restricted case where $K$ and $L$ are finite, and in the size of a DFA for $M$.</p>

<p>In a <a href="http://www.labri.fr/perso/tplace/Files/fsttcs13.pdf">2013 paper</a>, authors indicate:</p>

<blockquote>
  <p>Although the separation problem frequently occurs, it has however not been systematically
  studied, even in the restricted, yet still challenging case of regular languages.</p>
</blockquote>

<p>They however mention several special cases that have been solved, and that most certainly encompass the finite case.</p>

<p>You may also want to look at <a href="http://en.wikipedia.org/wiki/Craig_interpolation">Craig interpolant</a>, a similar problem on logical formulae.
Interpolation is used for instance in SAT-based model-checking, in a setting which I think is closer to what you are looking for (especially regarding finiteness of the input). <a href="http://www.kenmcmil.com/pubs/CAV03.pdf">This paper</a> should be a good starting point.</p>

CC BY-SA 3.0
2015-04-20T01:56:43.667Z
I appreciate that you shared this.  I didn't know about this paper.  Thank you.  :)
Michael Wehar
CC BY-SA 3.0
2015-04-15T08:08:15.167Z
2015-04-15T08:08:15.167Z
Boson
<p>There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length <span class="math-container">$n$</span>, how large of a DFA is required to &quot;separate&quot; them, meaning accept one string but reject the other.</p>
<p>Here are some relevant papers <a href="http://ac.els-cdn.com/0020019089902159/1-s2.0-0020019089902159-main.pdf?_tid=443e0384-e327-11e4-9ba9-00000aab0f02&amp;acdnat=1429072031_920f725524e407becd4d55c06330fe19" rel="noreferrer">1</a>, <a href="https://cs.uwaterloo.ca/%7Eshallit/Talks/sep2.pdf" rel="noreferrer">2</a>. (I have a few more but I don't have enough reputation to post them).</p>
<p>These all discuss the problem of separating <em>two</em> distinct strings. I am wondering if there been any work done in the area of separating lists of strings, meaning given two lists of strings, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, what size DFA is required to accept every string in <span class="math-container">$A$</span> and reject every string in <span class="math-container">$B$</span>. This problem is equivalent to regex golf.</p>
<p>There are some basic questions that I have been working on such as if one of the lists is of size <span class="math-container">$1$</span> or if all the strings are of different lengths.</p>
<p>I have been searching around but haven't found any papers that deal with this type of problem. Has there been any research done in this area?</p>
<p>Thanks in advance.</p>

CC BY-SA 3.0
2015-04-16T02:09:43.817Z
fyi same as [minimal DFA given in-words & out-words](http://cstheory.stackexchange.com/questions/27971/minimal-finite-automata-given-in-words-and-out-words)
vzn
CC BY-SA 3.0
2015-04-20T01:23:14.093Z
VZN's link is great!  However, I believe you can find even more info if you take a look in the appendix of: "Computers and Intractability: A Guide to the Theory of NP-Completeness"
Michael Wehar
CC BY-SA 3.0
2015-04-20T01:26:10.593Z
Also, if you're interested in separating two lists with a linear time bounded Turing machines, I gave a little construction and posted the write-up online (it's nothing that special).  Basically, for two k element lists where each string has length at most n, you can separate the lists with a Turing machine that has $k\frac{log(n)}{log(log(n))}$ states and has an "optimal runtime".
Michael Wehar
CC BY-SA 3.0
2015-04-20T01:36:06.943Z
By Gold1978, we know that the problem of determining if two lists can be separated by a DFA of a given size is NP-complete.  If you modify the problem to say separated by a Turing machine with a time bound written in unary, then it's not known if the problem is NP-complete.  It's been suggested that this problem may be related to the minimum circuit problem in which case it would resolve open problems in structural complexity if you showed it was in P or if it was NP-complete.
Michael Wehar
CC BY-SA 3.0
2015-04-20T01:47:55.407Z
Also, if you're interested in separating lists of strings by automata with memory, non-determinism, or alternation then Dmitry's work may be of interest to you since counting is related to separting: http://drops.dagstuhl.de/opus/volltexte/2014/4854/pdf/30.pdf
Michael Wehar
CC BY-SA 3.0
2016-02-03T08:29:08.497Z
Possible duplicate of [Is finding the minimum regular expression an NP-complete problem?](http://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)
Boson
<fl.formal-languages><automata-theory>
Separating lists of words
MRC
# Separating lists of words

(Asked by: username_0 on 2015-04-15)

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, meaning accept one string but reject the other.

Here are some relevant papers [1](http://ac.els-cdn.com/0020019089902159/1-s2.0-0020019089902159-main.pdf?_tid=443e0384-e327-11e4-9ba9-00000aab0f02&acdnat=1429072031_920f725524e407becd4d55c06330fe19), [2](https://cs.uwaterloo.ca/%7Eshallit/Talks/sep2.pdf). (I have a few more but I don't have enough reputation to post them).

These all discuss the problem of separating *two* distinct strings. I am wondering if there been any work done in the area of separating lists of strings, meaning given two lists of strings, $A$ and $B$, what size DFA is required to accept every string in $A$ and reject every string in $B$. This problem is equivalent to regex golf.

There are some basic questions that I have been working on such as if one of the lists is of size $1$ or if all the strings are of different lengths.

I have been searching around but haven't found any papers that deal with this type of problem. Has there been any research done in this area?

Thanks in advance.

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: fyi same as [minimal DFA given in-words & out-words](http://cstheory.stackexchange.com/questions/27971/minimal-finite-automata-given-in-words-and-out-words)  
> **username_2**: VZN's link is great!  However, I believe you can find even more info if you take a look in the appendix of: "Computers and Intractability: A Guide to the Theory of NP-Completeness"  
> **username_2**: Also, if you're interested in separating two lists with a linear time bounded Turing machines, I gave a little construction and posted the write-up online (it's nothing that special).  Basically, for two k element lists where each string has length at most n, you can separate the lists with a Turing machine that has $k\frac{log(n)}{log(log(n))}$ states and has an "optimal runtime".  
> **username_2**: By Gold1978, we know that the problem of determining if two lists can be separated by a DFA of a given size is NP-complete.  If you modify the problem to say separated by a Turing machine with a time bound written in unary, then it's not known if the problem is NP-complete.  It's been suggested that this problem may be related to the minimum circuit problem in which case it would resolve open problems in structural complexity if you showed it was in P or if it was NP-complete.  
> **username_2**: Also, if you're interested in separating lists of strings by automata with memory, non-determinism, or alternation then Dmitry's work may be of interest to you since counting is related to separting: http://drops.dagstuhl.de/opus/volltexte/2014/4854/pdf/30.pdf  
> **username_3**: Possible duplicate of [Is finding the minimum regular expression an NP-complete problem?](http://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)  

---

## 2 answers

### Answer by username_3 on 2015-04-15. Score: 9 | Accepted answer

The question you are asking is known as the separation problem for languages: Given two languages $K$ and $L$, is there a third language $M$ (a separator) that separates them, i.e. $K \subseteq M$ and $M \cap L = \emptyset$.

You are interested in the restricted case where $K$ and $L$ are finite, and in the size of a DFA for $M$.

In a [2013 paper](http://www.labri.fr/perso/tplace/Files/fsttcs13.pdf), authors indicate:

> Although the separation problem frequently occurs, it has however not been systematically
> studied, even in the restricted, yet still challenging case of regular languages.

They however mention several special cases that have been solved, and that most certainly encompass the finite case.

You may also want to look at [Craig interpolant](http://en.wikipedia.org/wiki/Craig_interpolation), a similar problem on logical formulae.
Interpolation is used for instance in SAT-based model-checking, in a setting which I think is closer to what you are looking for (especially regarding finiteness of the input). [This paper](http://www.kenmcmil.com/pubs/CAV03.pdf) should be a good starting point.

> **Comments:**
> **username_2**: I appreciate that you shared this.  I didn't know about this paper.  Thank you.  :)  

---

### Answer by username_4 on 2015-04-15. Score: 3

The special case of having exactly one word in $A$ and one word in $B$ has [been mentioned here before](https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22494#22494).

This is called the "The Separating Words Problem". The slides by Shallit pretty much cover all that is known about the problem (see [slides1](https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf) and [slides2](https://cs.uwaterloo.ca/~shallit/Talks/bc4.pdf)).

> **Comments:**
> **username_2**: If you're interested in finding the smallest DFA for the special case see: http://cstheory.stackexchange.com/questions/29119/finding-the-smallest-dfa-that-separates-two-words-without-using-brute-force-sear  

---

