12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ possible duplicate of Is finding the minimum regular expression an NP-complete problem? $\endgroup$ – Tsuyoshi Ito Jan 19 '12 at 21:15
  • 2
    $\begingroup$ Lev’s well-written answer to the question I linked already covers inapproximability. $\endgroup$ – Tsuyoshi Ito Jan 19 '12 at 22:02
  • 6
    $\begingroup$ I also wrote a blog post that goes into more detail than my original answer cstheory.blogoverflow.com/2011/08/on-learning-regular-languages $\endgroup$ – Lev Reyzin Jan 19 '12 at 22:55
  • 1
    $\begingroup$ I fail to see the difference between “your version” and the inapproximability result Lev cited in the answer. In addition, I fail to see the connection between “your version” and “going the other way.” $\endgroup$ – Tsuyoshi Ito Jan 20 '12 at 12:39
  • 1
    $\begingroup$ @TsuyoshiIto Actually, it appears Lev's answer does answer "my version"! I was reading the blog post above, and it didn't (at least, I didn't find it). But Lev's original answer did. As for the connection between "my version" and "going the other way"... If we can generate such $A$ and $B$, it means that the answer to the "my version" isn't always negative. Parekh and Honavar's paper actually use this idea to prove that simple DFA are learnable with arbitrarily high probability. In any case, how does one or how should one close this question? $\endgroup$ – Francisco Mota Jan 21 '12 at 1:06
5
$\begingroup$

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:

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ your second link just links to this question. Where is it suppose to link? $\endgroup$ – Artem Kaznatcheev May 14 '12 at 1:24
  • $\begingroup$ oops, thx, fixed $\endgroup$ – vzn May 14 '12 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.