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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
||||||||||||||||||
|
|
7
|
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). |
||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
5
|
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, ...".) |
||
|
|
