My reply to nmrm might answer your question.
Finding some regular expression that matches all of the positive examples and does not match all of the negative examples is trivial. Finding a good regular expression that does that is not.
State minimization does not mitigate this problem. As an aside, state minimization is a polynomial algorithm.
Given the positive examples:
aba
abaa
aaaaba
and the negative examples:
abba
ba
ab
we could make a regex that does something like ("aba" | "abaa" | "aaaaba") & !("abba" | "ba" | "ab"), but unfortunately, running a state minimization algorithm on this regex does not give you "a+ba+" because the two regex are not equivalent (they do not accept the same language).
So you can find plenty of regex that will match your examples and not match your counterexamples, but you cannot easily minimize them to what you do want.
