I answer the learning-related aspects of the question.

This problem seems to be called “DFA learning” in the literature.

Gold [Gol78] showed that it is NP-complete to decide, given k∈ℕ and two finite sets P and N of strings, whether there exists a deterministic finite-state automaton (DFA) with at most k states which accepts every string in P and none of the strings in N. The paper [PH01] seems to discuss problems related to this motivation (there may be many more; this just came up when I tried to find relevant papers with Google).

References

[Gol78] E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh and Vasant Honavar. Learning DFA from simple examples. Machine Learning, 44(1–2):9–35, July 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh-dfa.pdf

I answer the learning-related aspects of the question.

This problem seems to be called “DFA learning” in the literature.

Gold [Gol78] showed that it is NP-complete to decide, given $k \in \mathbb{N}$ and two finite sets $P$ and $N$ of strings, whether there exists a deterministic finite-state automaton (DFA) with at most $k$ states which accepts every string in $P$ and none of the strings in $N$. The paper [PH01] seems to discuss problems related to this motivation (there may be many more; this just came up when I tried to find relevant papers with Google).

References

[Gol78] E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978.
https://doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh and Vasant Honavar. Learning DFA from simple examples. Machine Learning, 44(1–2):9–35, July 2001.
https://doi.org/10.1007/3-540-63577-7_39
http://faculty.ist.psu.edu/vhonavar/Papers/ALT97.ps