minimal finite automata given in-words and out-words

Question

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.

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 02: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 05 '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 07 '15 at 16:09

score 8 · Accepted Answer · answered Dec 29 '14 at 20:36

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

The key point to note is that a DFA accepting the positive instances and nothing else (which can be constructed, via the Myhill-Nerode theorem, in polynomial time) may be much larger than a DFA that accepts some superset of the positive instances, but still doesn't accept any of the negative instances. Intuitively, this problem is hard because the search is over the exponential sized collection of supersets of the positive instances that are also subsets of the complement of the negative instances. — András Salamon, Dec 31 '14 at 17:22

minimal finite automata given in-words and out-words

1 Answers1

Linked