Minimal DFA satisfying a finite view of a language
As you already know from the comments, finding the minimal DFA satisfying a finite set of positive and negative examples is $\mathsf{NP}$-hard. However, not all hope is lost, if you are willing to modify your learning paradigm slightly then we can get back into $\mathsf{P}$.

Assume that you are trying to learn a an unknown DFA $W$ which is minimal for some language $L_W$. If you allow the oracle membership queries and to act as a teacher by answering the following question: Given a proposed DFA $G$ does it recognize $L_W$? If not, can you provide a counter-example?

Note that if the oracle has access to $W$ it can compare $G$ to $W$ in poly-time, since testing equality between regular languages is easy. Generating a counter-example can also be done in polynomial time.

In this framework, you can learn $W$ in polynomial time using Angluin's (1987; pdf) algorithm (or Schapire's refinement of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:


Lower bounds for learning in the membership query and counterexample model
Are there improvements on Dana Angluin's algorithm for learning regular sets