Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$ that are known to be in the language, and a finite set of strings $B \subseteq (\Sigma^* \setminus L)$ that are known to not be in the language.

For example, let's say I have the $A = \{ab, aaab, aaaaabb\}$ and $B = \{b, aab, aaaba\}$. I might have the language $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, since $A$ and $B$ are consistent with $L$, or I might have a completely different language.

My question is: is there a known way to create a DFA (deterministic finite automata) that accepts the strings in $A$ and rejects the strings in $B$, with a minimal or almost-minimal number of states? What's the complexity of this problem? How good is it at approximating $L$ (assuming $L$ has a fairly low descriptive complexity, and $A$ and $B$ are large)?

I wasn't sure if this was research-level for cstheory.stackexchange.com, so I'm posting here. I've taken a stab at trying to find an answer for this question, but I honestly have no idea where to look.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I moved this question to cstheory.stackexchange.com (here), where it turned out to be a near-duplicate of another question. Lev Reyzen wrote a good blog post about that question.

This problem is NP-hard, and therefore intractable (assuming P != NP). So probably the most efficient method of generating such a DFA is by brute force.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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