minimal finite automata given in-words and out-words
If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete 

Gold1978 - Complexity of Automaton Identification from Given Data. 

The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of states is an approximation of the number of states of a minimum consistent DFA. 

Pitt-Warmuth-1993 - The minimum consistent DFA problem cannot be approximated within any polynomial.

There are many known heuristics and algorithms for tackling this problems. A well studied algorithm is due to Angluin.

Angluin-1987 - Learning regular sets from queries and counterexamples