<p>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}$.</p>

<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 <em>and</em> 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?</p>

<p>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.</p>

<p>In this framework, you can learn $W$ in polynomial time using Angluin's (<a href="http://www.sciencedirect.com/science/article/pii/0890540187900526" rel="nofollow noreferrer">1987</a>; <a href="http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf" rel="nofollow noreferrer">pdf</a>) algorithm (or <a href="http://dl.acm.org/citation.cfm?id=136314" rel="nofollow noreferrer">Schapire's refinement</a> of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:</p>

<ul>
<li><p><a href="https://cstheory.stackexchange.com/q/10958/1037">Lower bounds for learning in the membership query and counterexample model</a></p></li>
<li><p><a href="https://cs.stackexchange.com/q/118/55">Are there improvements on Dana Angluin's algorithm for learning regular sets</a></p></li>
</ul>

CC BY-SA 3.0
2012-05-14T01:23:54.070Z
2012-05-14T01:23:54.070Z
2017-04-13T12:48:30.830Z
Artem Kaznatcheev
<p>It seems to me that you can use a refinement of Myhill-Nerode equivalence for this problem.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-05-12T18:37:54.743Z
2012-05-12T18:37:54.743Z
Denis
<p>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. </p>

<p>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&amp;T FSM library is good for work in this area.</p>

<p>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.</p>

<p>[1] 
<a href="http://www.sciencedirect.com/science/article/pii/0893608095000410" rel="nofollow">Learning a class of large finite state machines with a recurrent neural network
C. Lee Giles, 1, B.G. Horne, T. Lin 1995</a></p>

<p>[2] <a href="http://authors.library.caltech.edu/13654/1/ZENnc93.pdf" rel="nofollow">Learning FSMs with self-clustering recurrent networks </a> by Zeng &amp; Smyth 1993</p>

<p>[3] <a href="http://www2.research.att.com/~fsmtools/fsm/" rel="nofollow">AT&amp;T FSM library</a></p>

CC BY-SA 3.0
2012-05-14T01:24:41.993Z
your second link just links to this question. Where is it suppose to link?
Artem Kaznatcheev
CC BY-SA 3.0
2012-05-14T04:28:22.237Z
oops, thx, fixed
vzn
CC BY-SA 3.0
2012-05-13T18:55:14.983Z
2012-05-14T20:04:41.797Z
2012-05-14T20:04:41.797Z
vzn
<p>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.</p>

<p>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.</p>

<p>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)?</p>

<p><a href="https://math.stackexchange.com/q/100278/23203">Original question on math.stackexchange.com.</a> 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.</p>

CC BY-SA 3.0
2012-01-19T21:15:41.690Z
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)
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-19T22:00:18.360Z
It's a near duplicate. I see two differences: a) I'm also interested in almost-minimal DFA (which is an ill-defined notion, but intuitive). b) I'm also interested in accuracy -- how good is the approximation? Either way, I thank you for the link to the previous post, there's a lot of information there that I'd like to absorb, and I support closing this question.
Francisco Mota
CC BY-SA 3.0
2012-01-19T22:02:18.073Z
Lev’s well-written answer to the question I linked already covers inapproximability.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-19T22:55:28.813Z
I also wrote a blog post that goes into more detail than my original answer http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/
Lev Reyzin
CC BY-SA 3.0
2012-01-19T23:44:31.310Z
@TsuyoshiIto, I don't think it covers my particular version of that question, which mentions descriptive complexity. My version is: if $L$ has some low descriptive complexity, and $A$ and $B$ have a high descriptive complexity, can we find $L$ using $A$ and $B$ or approximate it almost perfectly using $A$ and $B$? We can try going the other way: knowing $L$, can we generate $A$ and $B$ such that the minimal DFA will accept $L$? This question boils down to whether there are regular languages which no minimal DFA accepts.
Francisco Mota
CC BY-SA 3.0
2012-01-20T12:39:26.293Z
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.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-21T01:06:07.200Z
@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?
Francisco Mota
CC BY-SA 3.0
2012-05-13T18:41:48.290Z
FM you seem to be interested in the case of _learning_ the FSM using some algorithm, with training examples. there can be no general algorithm that can succeed at this but it can succeed "in some cases" if there is some limitation on the structure of the examples/solution.
vzn
<cc.complexity-theory><fl.formal-languages><automata-theory>
Minimal DFA satisfying a finite view of a language
Francisco Mota
# Minimal DFA satisfying a finite view of a language

(Asked by: username_0 on 2012-01-19)

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.](https://math.stackexchange.com/q/100278/23203) 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.

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: 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)  
> **username_0**: It's a near duplicate. I see two differences: a) I'm also interested in almost-minimal DFA (which is an ill-defined notion, but intuitive). b) I'm also interested in accuracy -- how good is the approximation? Either way, I thank you for the link to the previous post, there's a lot of information there that I'd like to absorb, and I support closing this question.  
> **username_1**: Lev’s well-written answer to the question I linked already covers inapproximability.  
> **username_2**: I also wrote a blog post that goes into more detail than my original answer http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/  
> **username_0**: @TsuyoshiIto, I don't think it covers my particular version of that question, which mentions descriptive complexity. My version is: if $L$ has some low descriptive complexity, and $A$ and $B$ have a high descriptive complexity, can we find $L$ using $A$ and $B$ or approximate it almost perfectly using $A$ and $B$? We can try going the other way: knowing $L$, can we generate $A$ and $B$ such that the minimal DFA will accept $L$? This question boils down to whether there are regular languages which no minimal DFA accepts.  
> **username_1**: 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.”  
> **username_0**: @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?  
> **username_3**: FM you seem to be interested in the case of _learning_ the FSM using some algorithm, with training examples. there can be no general algorithm that can succeed at this but it can succeed "in some cases" if there is some limitation on the structure of the examples/solution.  

---

## 3 answers

### Answer by username_4 on 2012-05-14. Score: 5

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](http://www.sciencedirect.com/science/article/pii/0890540187900526); [pdf](http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf)) algorithm (or [Schapire's refinement](http://dl.acm.org/citation.cfm?id=136314) 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](https://cstheory.stackexchange.com/q/10958/1037)
* [Are there improvements on Dana Angluin's algorithm for learning regular sets](https://cs.stackexchange.com/q/118/55)


---

### Answer by username_5 on 2012-05-12. Score: 0

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 by username_3 on 2012-05-13. Score: -1

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](http://www.sciencedirect.com/science/article/pii/0893608095000410)

[2] [Learning FSMs with self-clustering recurrent networks](http://authors.library.caltech.edu/13654/1/ZENnc93.pdf)  by Zeng & Smyth 1993

[3] [AT&T FSM library](http://www2.research.att.com/~fsmtools/fsm/)

> **Comments:**
> **username_4**: your second link just links to this question. Where is it suppose to link?  
> **username_3**: oops, thx, fixed  

---

