<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem">Is finding the minimum regular expression an NP-complete problem?</a>  </p>
</blockquote>



<p>Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of <em>positive</em> and <em>negative</em> examples) be two disjoint finite sets of words over $\Sigma$. I say that a deterministic finite automaton (DFA) over $\Sigma$ is <em>acceptable</em> if it accepts all words of $P$ and rejects all words of $N$ (the behavior on words in $\Sigma^* \backslash (P \cup N)$ is unspecified).</p>

<p>What is the complexity, given $P$ and $N$, of building a minimal acceptable DFA? Can we say that the number of states of a minimal acceptable DFA expresses an interesting intrinsic property of $P$ and $N$? Does a minimal acceptable DFA generalize the sets $P$ and $N$ in a useful way? In other words, does the behavior of a minimal acceptable automaton on $\Sigma^* \backslash (P \cup N)$ reflect a reasonable rule to distinguish $P$ and $N$?</p>

<p>Here is a simple example to explain why I ask this question. If P = {abc, ade, aaaac} and N = {bac, bbe, baabb}, then a minimal acceptable DFA would be the one which only reads the first letter and either accepts or rejects; this represents the reasonable rule "words starting by 'a' are in $P$, words starting by 'b' are in $N$". Likewise, if $P = \{aaaa, cab, baa, aab\}$ and $N = \{aba, abb, bba, bb, cbac\}$, I would expect the minimal acceptable DFA to accept or reject based on the second letter. I wonder what is the expressiveness of DFAs to generalize this sort of examples.</p>

CC BY-SA 3.0
2012-10-17T17:09:01.063Z
can you tell us why you are interested in this problem?
Kaveh
CC BY-SA 3.0
2012-10-17T20:25:08.840Z
It is not clear which is your actual question and you might want to review http://cstheory.stackexchange.com/faq
.  I presume you intended to ask about the time complexity (in terms of the size of $P$ and $N$) of deciding whether there is an acceptable DFA with at most $N_0$ states, where $N_0$ is part of the input.  Or were you interested in another question?
András Salamon
CC BY-SA 3.0
2012-10-17T23:30:24.760Z
In addition to the link suggested by Tsuyoshi Ito, you might also be interested in a blog post based on that question and the discussion it generated: http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/
András Salamon
CC BY-SA 3.0
2012-10-18T07:08:42.390Z
Yes, Tsuyoshi, this is actually a duplicate. Don't hesitate to close this question or submit your comment as an answer. Thanks a lot for pointing this out!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-10-21T03:29:17.583Z
It seems that [the same question](http://cstheory.stackexchange.com/q/13970/) is asked by someone else recently.
Kaveh
<fl.formal-languages><automata-theory><machine-learning><lg.learning>
Generalizing a set of positive and negative examples through DFAs
Antoine Amarilli 'a3nm'
# Generalizing a set of positive and negative examples through DFAs

(Asked by: username_0 on 2012-10-17)

> **Possible Duplicate:**  
> [Is finding the minimum regular expression an NP-complete problem?](https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)

Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of *positive* and *negative* examples) be two disjoint finite sets of words over $\Sigma$. I say that a deterministic finite automaton (DFA) over $\Sigma$ is *acceptable* if it accepts all words of $P$ and rejects all words of $N$ (the behavior on words in $\Sigma^\* \backslash (P \cup N)$ is unspecified).

What is the complexity, given $P$ and $N$, of building a minimal acceptable DFA? Can we say that the number of states of a minimal acceptable DFA expresses an interesting intrinsic property of $P$ and $N$? Does a minimal acceptable DFA generalize the sets $P$ and $N$ in a useful way? In other words, does the behavior of a minimal acceptable automaton on $\Sigma^\* \backslash (P \cup N)$ reflect a reasonable rule to distinguish $P$ and $N$?

Here is a simple example to explain why I ask this question. If P = {abc, ade, aaaac} and N = {bac, bbe, baabb}, then a minimal acceptable DFA would be the one which only reads the first letter and either accepts or rejects; this represents the reasonable rule "words starting by 'a' are in $P$, words starting by 'b' are in $N$". Likewise, if $P = \{aaaa, cab, baa, aab\}$ and $N = \{aba, abb, bba, bb, cbac\}$, I would expect the minimal acceptable DFA to accept or reject based on the second letter. I wonder what is the expressiveness of DFAs to generalize this sort of examples.

**Tags:** fl.formal-languages, automata-theory, machine-learning, lg.learning

> **Comments:**
> **username_1**: can you tell us why you are interested in this problem?  
> **username_2**: It is not clear which is your actual question and you might want to review http://cstheory.stackexchange.com/faq .  I presume you intended to ask about the time complexity (in terms of the size of $P$ and $N$) of deciding whether there is an acceptable DFA with at most $N_0$ states, where $N_0$ is part of the input.  Or were you interested in another question?  
> **username_2**: In addition to the link suggested by Tsuyoshi Ito, you might also be interested in a blog post based on that question and the discussion it generated: http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/  
> **username_0**: Yes, Tsuyoshi, this is actually a duplicate. Don't hesitate to close this question or submit your comment as an answer. Thanks a lot for pointing this out!  
> **username_1**: It seems that [the same question](http://cstheory.stackexchange.com/q/13970/) is asked by someone else recently.  

---

## 0 answers

