<p>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 </p>

<p><a href="http://www-personal.umich.edu/~yinw/papers/Gold78.pdf">Gold1978 - Complexity of Automaton Identification from Given Data</a>. </p>

<p>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. </p>

<p><a href="https://users.soe.ucsc.edu/~manfred/pubs/J22.pdf">Pitt-Warmuth-1993 - The minimum consistent DFA problem cannot be approximated within any polynomial</a>.</p>

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

<p><a href="http://www.sciencedirect.com/science/article/pii/0890540187900526">Angluin-1987 - Learning regular sets from queries and counterexamples</a></p>

CC BY-SA 3.0
2014-12-31T17:22:36.047Z
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
CC BY-SA 3.0
2014-12-29T20:36:34.070Z
2014-12-29T20:36:34.070Z
Mateus de Oliveira Oliveira
<p>this seems an interesting <a href="http://en.wikipedia.org/wiki/Finite-state_machine" rel="nofollow">FSM</a> optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. </p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2014-12-27T00:53:49.310Z
1. You might be interested in [Is regex golf NP-Complete?](http://cs.stackexchange.com/q/19686/755).  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.
CC BY-SA 3.0
2014-12-27T13:33:01.327Z
I think this is an extension of the problem of [separating strings with automata.](http://www.sciencedirect.com/science/article/pii/0020019089902159)
Shaull
CC BY-SA 3.0
2014-12-28T02:34:14.987Z
it is known computing [minimal NFAs](http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa) 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
CC BY-SA 3.0
2015-01-05T16:36:47.157Z
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
CC BY-SA 3.0
2015-01-07T16:09:54.473Z
realized this may be somewhat connected to [Hidden Markov models](http://en.wikipedia.org/wiki/Hidden_Markov_model) theory. eg in this recent paper [Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets](http://arxiv.org/abs/1501.01300) Paulson/ Griffin
vzn
<reference-request><optimization><machine-learning><regular-language><nondeterminism>
minimal finite automata given in-words and out-words
vzn
# minimal finite automata given in-words and out-words

(Asked by: username_0 on 2014-12-26)

this seems an interesting [FSM](http://en.wikipedia.org/wiki/Finite-state_machine) 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.

**Tags:** reference-request, optimization, machine-learning, regular-language, nondeterminism

> **Comments:**
> **username_1**: 1. You might be interested in [Is regex golf NP-Complete?](http://cs.stackexchange.com/q/19686/755).  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?  
> **username_2**: I think this is an extension of the problem of [separating strings with automata.](http://www.sciencedirect.com/science/article/pii/0020019089902159)  
> **username_0**: it is known computing [minimal NFAs](http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa) 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.  
> **username_3**: 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!  
> **username_0**: realized this may be somewhat connected to [Hidden Markov models](http://en.wikipedia.org/wiki/Hidden_Markov_model) theory. eg in this recent paper [Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets](http://arxiv.org/abs/1501.01300) Paulson/ Griffin  

---

## 1 answers

### Answer by username_4 on 2014-12-29. Score: 8 | Accepted answer

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](http://www-personal.umich.edu/~yinw/papers/Gold78.pdf).

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](https://users.soe.ucsc.edu/~manfred/pubs/J22.pdf).

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](http://www.sciencedirect.com/science/article/pii/0890540187900526)

> **Comments:**
> **username_5**: 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.  

---

