# minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.

given: two finite sets of words $S_{in}$ and $S_{out}$. find the smallest FSM with language $L$ such that for each $x \in S_{in}$, $x \in L$ and for each $y \in S_{out}$, $y \notin L$.

in other words one is given finite lists of words that are in the language and not in the language. there is a simple algorithm of creating an FSM with the given (non)acceptance and then minimizing it, but is this also the smallest possible? it seems to come down some to the question of cycles in the FSM graph. the simple strategy will not have cycles, so could smaller FSMs with cycles exist? there is also the question of nondeterminism.

• 1. You might be interested in Is regex golf NP-Complete?. It's not exactly the same thing, but it's related (it's for regexes rather than DFA). 2. Please specify precisely what you mean by a FSM. Do you mean a DFA? or a NFA? – D.W. Dec 27 '14 at 0:53
• I think this is an extension of the problem of separating strings with automata. – Shaull Dec 27 '14 at 13:33
• it is known computing minimal NFAs is rather difficult. am ok with partial answer(s) that focus on the simpler DFA case. also there are interesting natural lower bounds/ "compressibility" questions that some word sets are "harder" than others ie lead to (much?) more states than others. – vzn Dec 28 '14 at 2:34
• I'm quite interested in these three problems. Please feel free to contact me if you are too. (1) Minimum PDA given in-words and out-words. (2) Minimum DFA given 1 in-word and 1 out-word. (3) Minimum Turing machine given time bound and in-words and out-words. Thanks! – Michael Wehar Jan 5 '15 at 16:36
• realized this may be somewhat connected to Hidden Markov models theory. eg in this recent paper Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets Paulson/ Griffin – vzn Jan 7 '15 at 16:09