<p>If I understand your question correctly, it is shown in the following paper that it is an NP-complete problem:</p>

<p>E. Mark Gold: Complexity of Automaton Identification from Given Data Information and Control 37(3): 302-320 (1978)</p>

CC BY-SA 3.0
2012-10-16T18:05:45.750Z
I'll have to look into it tomorrow at school, thanks anyways!
yo'
CC BY-SA 3.0
2012-10-16T17:22:58.150Z
2012-10-16T17:22:58.150Z
Guy
<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem">Is finding the minimum regular expression an NP-complete problem?</a>  </p>
</blockquote>



<p>Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of words $\mathcal I$ and $\mathcal O$ that are and aren't in the langueage, respectively. This means: $\mathcal I\subset\mathcal L$ and $\mathcal O\cap \mathcal L=\emptyset$.</p>

<p>Is there an algorithm that would try to generate the simplest possible automaton such that it accepts words in $\mathcal I$ and denies words in $\mathcal O$?</p>

<p>I know that there's no single automaton for any such case, but I believe my language is quite and the automaton should be simple as well.</p>

<p>My idea in the background is that I don't know the language, I have a program that enumerates it. I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton.</p>

<p><em>(NB: If this belongs to CS.SE, feel free to migrate it.)</em></p>

CC BY-SA 3.0
2012-10-16T15:52:12.973Z
So given two finite lists of words $I,O$, you want to find the smallest DFA (or NFA?) that accepts all words in $I$ and rejects all words in $O$. Sounds hard.
Yuval Filmus
CC BY-SA 3.0
2012-10-16T18:12:22.023Z
How are the  sets represented? If they are finite then obviously they are regular. If they are infinite then the answer will depend on how tjey are represented and is likely to be undecidable.
Kaveh
CC BY-SA 3.0
2012-10-16T18:31:28.083Z
There is a lot of theory of on learning automata. Look at http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/j/Jonsson:Bengt.html. He does work in the area.
Dave Clarke
CC BY-SA 3.0
2012-10-16T18:36:26.270Z
@Kaveh The sets are finite and they are generated by a C++ program. I know they are regular, I think that you misunderstood my question. Yuval Filmus stated it very shortly and precisely.
yo'
CC BY-SA 3.0
2012-10-16T20:54:41.117Z
then you should modify the question and make it more precise according yo Yuval's comment and remove "I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton."
Kaveh
CC BY-SA 3.0
2012-10-21T03:30:53.197Z
[Generalizing a set of positive and negative examples through DFAs](http://cstheory.stackexchange.com/q/13985/). I am interested to know what is the reason of this sudden interest in this question.
Kaveh
CC BY-SA 3.0
2012-10-21T07:42:32.790Z
@Kaveh I can explain you simply: It's "laziness". Having a good positive result, you can --- instead of really describing the language you want to study --- simply enumerate enough words in/out the language and let the computer do your job. Once you have an automaton, it's much easier to prove it's _the_ automaton.
yo'
<fl.formal-languages><automata-theory><regular-language>
Getting an automaton from set of words in and out of a language
yo'
# Getting an automaton from set of words in and out of a language

(Asked by: username_0 on 2012-10-16)

> **Possible Duplicate:**  
> [Is finding the minimum regular expression an NP-complete problem?](https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)

Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of words $\mathcal I$ and $\mathcal O$ that are and aren't in the langueage, respectively. This means: $\mathcal I\subset\mathcal L$ and $\mathcal O\cap \mathcal L=\emptyset$.

Is there an algorithm that would try to generate the simplest possible automaton such that it accepts words in $\mathcal I$ and denies words in $\mathcal O$?

I know that there's no single automaton for any such case, but I believe my language is quite and the automaton should be simple as well.

My idea in the background is that I don't know the language, I have a program that enumerates it. I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton.

*(NB: If this belongs to CS.SE, feel free to migrate it.)*

**Tags:** fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_1**: So given two finite lists of words $I,O$, you want to find the smallest DFA (or NFA?) that accepts all words in $I$ and rejects all words in $O$. Sounds hard.  
> **username_2**: How are the  sets represented? If they are finite then obviously they are regular. If they are infinite then the answer will depend on how tjey are represented and is likely to be undecidable.  
> **username_3**: There is a lot of theory of on learning automata. Look at http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/j/Jonsson:Bengt.html. He does work in the area.  
> **username_0**: @Kaveh The sets are finite and they are generated by a C++ program. I know they are regular, I think that you misunderstood my question. Yuval Filmus stated it very shortly and precisely.  
> **username_2**: then you should modify the question and make it more precise according yo Yuval's comment and remove "I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton."  
> **username_2**: [Generalizing a set of positive and negative examples through DFAs](http://cstheory.stackexchange.com/q/13985/). I am interested to know what is the reason of this sudden interest in this question.  
> **username_0**: @Kaveh I can explain you simply: It's "laziness". Having a good positive result, you can --- instead of really describing the language you want to study --- simply enumerate enough words in/out the language and let the computer do your job. Once you have an automaton, it's much easier to prove it's _the_ automaton.  

---

## 1 answers

### Answer by username_4 on 2012-10-16. Score: 3

If I understand your question correctly, it is shown in the following paper that it is an NP-complete problem:

E. Mark Gold: Complexity of Automaton Identification from Given Data Information and Control 37(3): 302-320 (1978)

> **Comments:**
> **username_0**: I'll have to look into it tomorrow at school, thanks anyways!  

---

