0
$\begingroup$

Possible Duplicate:
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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ can you tell us why you are interested in this problem? $\endgroup$
    – Kaveh
    Oct 17, 2012 at 17:09
  • $\begingroup$ It is not clear which is your actual question and you might want to review 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? $\endgroup$
    – András Salamon
    Oct 17, 2012 at 20:25
  • 2
    $\begingroup$ 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: cstheory.blogoverflow.com/2011/08/on-learning-regular-languages $\endgroup$
    – András Salamon
    Oct 17, 2012 at 23:30
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Oct 18, 2012 at 7:08
  • $\begingroup$ It seems that the same question is asked by someone else recently. $\endgroup$
    – Kaveh
    Oct 21, 2012 at 3:29

0

Reset to default