# Getting an automaton from set of words in and out of a language [duplicate]

Possible Duplicate:
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.)

• 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 Oct 16 '12 at 15:52
• 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 Oct 16 '12 at 18:12
• There is a lot of theory of on learning automata. Look at informatik.uni-trier.de/~ley/db/indices/a-tree/j/…. He does work in the area. – Dave Clarke Oct 16 '12 at 18:31
• @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' Oct 16 '12 at 18:36
• @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' Oct 21 '12 at 7:42