11
$\begingroup$

Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus B$?

In other words, $A$ represents a set of positive examples. Every string in $A$ needs to be accepted by the DFA. $B$ represents a set of negative examples. No string in $B$ should be accepted by the DFA.

Is there a way to solve this, perhaps using DFA minimization techniques? I could imagine creating a DFA-like automaton that has three kinds of states: accept states, reject states, and "don't-care" states (any input that ends in a "don't-care" state can be either accepted or rejected). But can we then find a way to minimize this to an ordinary DFA?

You could think of this as the problem of learning a DFA, given positive and negative examples.

This is inspired by Is regex golf NP-Complete?, which asks a similar questions for regexps instead of DFAs.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think you'll need to put some sort of restriction on what sorts of languages $A$ and $B$ may be and how they may be specified. $\endgroup$
    – reinierpost
    Jan 13, 2014 at 10:25
  • $\begingroup$ There is a lot of literature on learning functions/languages, e.g. filed under learning in the limit (also Gold-style learning). These don't fit your problem exactly but may be interesting. $\endgroup$
    – Raphael ♦
    Jan 13, 2014 at 12:54

2 Answers 2

Reset to default
7
$\begingroup$

A DFA as you describe is called a separating DFA. There is some literature on this problem when $A$ and $B$ are regular languages, such as Learning Minimal Separating DFA’s for Compositional Verification, by Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang

Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If A and B are both regular languages, and if one is allowed to arbitrarily accept or reject any input for which A and B would yield the same result, I don't see how the problem could be undecidable. For a DFA of any particular size, it would be possible to construct a fully comprehensive set of inputs it should accept and inputs that it should reject, such that any DFA with the same number of states or fewer that correctly handles all of the test cases can be guaranteed to behave identically in all cases. Since a machine that accepts everything A accepts and rejects everything else would... $\endgroup$
    – supercat
    Nov 23, 2014 at 20:07
  • $\begingroup$ ...satisfy the constraints, one can put an upper limit on the number of states a machine would have to contain; since there are a finite number of possible machines of any given size, and a finite number of test cases to be evaluated, one could generate all possible machines which are smaller than A and see if any of them meet the necessary conditions. Not exactly a speedy way of solving the problem, but certainly decidable if A and B are regular. If they're not regular, a DFA wouldn't be able to solve A or B. The "difference" might sometimes be regular even if A and B aren't, but that... $\endgroup$
    – supercat
    Nov 23, 2014 at 20:09
  • $\begingroup$ ...would be an "unusual" case. $\endgroup$
    – supercat
    Nov 23, 2014 at 20:12
8
$\begingroup$

There is a lot of literature on learning DFAs given positive and negative samples. If $A$ and $B$ are finite I don't see how the problem would ever be undecidable though. If $A \cap B = \emptyset$ then obviously the DFA that accepts only the strings in $A$ satisfies your requirement and one can simply enumerate all smaller DFAs. If $A \cap B \neq \emptyset$ then clearly no such DFA exists.

Finding the minimum DFA consistent with a given set of strings is NP-complete. This result appears as Theorem 1 in Angluin's paper On the complexity of minimum inference of regular sets. So clearly your problem is also NP-complete.

For lots of good links and discussion on learning regular languages check out the CSTheory blogpost On Learning Regular Languages.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If the requirements were changed so that an automaton could arbitrarily accept or reject anything which is in both A and B, then the problem would always be solvable for any A and B; if finding the optimal automaton would be NP-complete without doing that, it would be NP-complete even with that requirement. $\endgroup$
    – supercat
    Nov 23, 2014 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.