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?



Is there an algorithm that can "reverse engineer" a Regular Expression?
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)](http://www.informatik.uni-trier.de/~fernau/papers/Fer05c.pdf).


