Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?

share|improve this question
1  
A regular language is not determined by finitely many words it does or does not contain. Are you given an a priori bound on the size of the automaton? (If so, you can in the worst case search exhaustively.) –  Qiaochu Yuan May 26 '12 at 3:41
    
I feel like there ought to be a Bayesian approach to this problem. –  David Cohen May 26 '12 at 5:13
    
The following by Christoph Koutchan might be helpful: risc.jku.at/publications/download/risc_3078/… although I guess that a lot of work would remain to make it applicable to your setting. –  Martin Rubey May 26 '12 at 6:40
    
What about an infinite language union some large word? –  joro May 26 '12 at 6:42
    
the title doesn't really fit the question. –  Ale De Luca May 26 '12 at 6:58

2 Answers 2

up vote 7 down vote accepted

Without additional assumptions there is no such algorithm. In finite time an alleged algorithm could only test for finitely many inputs, but since there are infinitely many regular languages which match any given finite number of test cases, the algorithm cannot work.

In machine learning this is a common situation (given these finitely many cases of a function, "learn" the function on the rest of infinitely many cases). You should look at machine learning literature, as this is what you are doing. For example, you could ask, what is the simplest regular expression which matches the given test cases?

And just to demonstrate that Google is not that hard to use, here is the first hit on "learn regular expression machine learning": Henning Fernau, Algorithms for Learning Regular Expressions (Extended Abstract).

share|improve this answer
    
Thanks. I guess the best assumption would be a bound on the number of states. If this is given - say k, one can enumerate over all pairs of such automata (modulo equivalence), and for each pair test a word that separates it. Only one automaton will survive. –  Golan May 27 '12 at 17:02
    
You could do that, but the combinatorial explosion will prevent you from getting very far. It would help to know what your motivation for this question is. –  Andrej Bauer May 27 '12 at 18:34

There is no such algorithm. As an explicit example, imagine a black box that always says yes. How many inputs should this algorithm test before it concludes that the language contains all words?

(NB: You write "given a language, is there an algorithm...". I read this as "Is there an algorithm which, given a language, ...".)

share|improve this answer

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.