An example distribution for probabilistic query learning of simple deterministic languages
Yasuhiro Tajima, Genichiro Kikui · International Colloquium on Grammatical Inference · 2014
In this paper, we show a special example distribution on which the learner can guess a correct simple deterministic grammar in polynomial time from membership queries and random examples. At rst, we show a learning algorithm of simple deterministic languages from membership and equivalence queries. This algorithm is not a polynomial time algorithm but, assuming a special example distribution, we can modify it to the polynomial time probabilistic learning algorithm.