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

Improve this question
$\endgroup$
7
  • 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
    Commented Oct 16, 2012 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
    Commented Oct 16, 2012 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
    Commented Oct 16, 2012 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'
    Commented Oct 16, 2012 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'
    Commented Oct 21, 2012 at 7:42

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'll have to look into it tomorrow at school, thanks anyways! $\endgroup$
    – yo'
    Commented Oct 16, 2012 at 18:05

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