Separating lists of words 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 &quot;separate&quot; them, meaning accept one string but reject the other.
Here are some relevant papers 1, 2. (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.
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, 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, 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 should be a good starting point.