Minimal DFA satisfying a finite view of a language

Question

Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$ that are known to be in the language, and a finite set of strings $B \subseteq (\Sigma^* \setminus L)$ that are known to not be in the language.

For example, let's say I have the $A = \{ab, aaab, aaaaabb\}$ and $B = \{b, aab, aaaba\}$. I might have the language $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, since $A$ and $B$ are consistent with $L$, or I might have a completely different language.

My question is: is there a known way to create a DFA (deterministic finite automata) that accepts the strings in $A$ and rejects the strings in $B$, with a minimal or almost-minimal number of states? What's the complexity of this problem? How good is it at approximating $L$ (assuming $L$ has a fairly low descriptive complexity, and $A$ and $B$ are large)?

Original question on math.stackexchange.com. I decided to repost here after getting no answers on the original question, and having no idea where to look for them. If someone could point me toward research in this area, it would be greatly appreciated.

Answer 1

As you already know from the comments, finding the minimal DFA satisfying a finite set of positive and negative examples is $\mathsf{NP}$-hard. However, not all hope is lost, if you are willing to modify your learning paradigm slightly then we can get back into $\mathsf{P}$.

Assume that you are trying to learn a an unknown DFA $W$ which is minimal for some language $L_W$. If you allow the oracle membership queries and to act as a teacher by answering the following question: Given a proposed DFA $G$ does it recognize $L_W$? If not, can you provide a counter-example?

Note that if the oracle has access to $W$ it can compare $G$ to $W$ in poly-time, since testing equality between regular languages is easy. Generating a counter-example can also be done in polynomial time.

In this framework, you can learn $W$ in polynomial time using Angluin's (1987; pdf) algorithm (or Schapire's refinement of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:

• Lower bounds for learning in the membership query and counterexample model

• Are there improvements on Dana Angluin's algorithm for learning regular sets

Answer 2

It seems to me that you can use a refinement of Myhill-Nerode equivalence for this problem.

We can define $u\nsim v$ if there exists $x\in\Sigma$ such that $ux\in A$ and $vx\in B$. This means that any automaton separating $A$ from $B$ must be in different states after reading $u$ and $v$.

It suffices to study this relation over prefixes of elements of $A$ and $B$. This will give you a lower bound on the number of states you need. I'm not sure it directly gives you a way to build the minimal automaton, but it is at least a path to explore.

Answer 3

I think this problem may have been inexactly phrased by the questioner. The questioner apparently wants an algorithm that generalizes infinite words based on specific finite word examples, using some kind of mechanized induction, i.e. recognizing apparent patterns in the examples.

In addition to some CS theory research cited in comments, there is also some more empirical research in this area e.g. below, using ANNs to create FSMs from examples. Note one can always run a standard DFA minimization algorithm on the result. The AT&T FSM library is good for work in this area.

The questioner is not specific about his problem domain, that can help to understand the structure of examples and get more specific references. However, one example that can be seen is AI algorithms in games that use FSM algorithms. I suspect there are some cases where the FSMs are learned from examples using learning algorithms.

[1] Learning a class of large finite state machines with a recurrent neural network C. Lee Giles, 1, B.G. Horne, T. Lin 1995

[2] Learning FSMs with self-clustering recurrent networks by Zeng & Smyth 1993

[3] AT&T FSM library