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