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?
7
-
3$\begingroup$ 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.) $\endgroup$– Qiaochu YuanCommented May 26, 2012 at 3:41
-
$\begingroup$ I feel like there ought to be a Bayesian approach to this problem. $\endgroup$– David CohenCommented May 26, 2012 at 5:13
-
$\begingroup$ 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. $\endgroup$– Martin RubeyCommented May 26, 2012 at 6:40
-
$\begingroup$ What about an infinite language union some large word? $\endgroup$– joroCommented May 26, 2012 at 6:42
-
1$\begingroup$ See cstheory.stackexchange.com/questions/1854/… $\endgroup$– David E SpeyerCommented May 26, 2012 at 12:02
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
2
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).
answered May 26, 2012 at 6:42
-
$\begingroup$ 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. $\endgroup$– GolanCommented May 27, 2012 at 17:02
-
$\begingroup$ 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. $\endgroup$ Commented May 27, 2012 at 18:34
$\begingroup$
$\endgroup$
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, ...".)
$\begingroup$
$\endgroup$
You can only do that under 2 assumptions:
- You know ahead the lenght of the regular expression
- You can compare the execution tree of a black-box attemp with any previous attemp
As you know regular expressions are FSM.
By execution tree I mean the following:
- The machine enter a state and stay there some time (re-entering same state as many times it wish)
- Then enter another state and so on.
- Each execution tree is a tuple of N elements, and you can compare each element for equality with other elements of same or other tuples (necessary to detect loops).
Alternatively:
- You know ahead the lenght of the regular expression
- There are no loops in the FSM
