4
$\begingroup$

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.)

$\endgroup$

marked as duplicate by Tsuyoshi Ito, Kaveh Dec 6 '12 at 7:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 16 '12 at 15:52
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 16 '12 at 18:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Dave Clarke Oct 16 '12 at 18:31
  • $\begingroup$ @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. $\endgroup$ – yo' Oct 16 '12 at 18:36
  • 1
    $\begingroup$ @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. $\endgroup$ – yo' Oct 21 '12 at 7:42
3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ I'll have to look into it tomorrow at school, thanks anyways! $\endgroup$ – yo' Oct 16 '12 at 18:05

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