An example distribution for probabilistic query learning of simple deterministic languages


Yasuhiro Tajima, Genichiro Kikui ;
The 12th International Conference on Grammatical Inference, PMLR 34:182-192, 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 first, 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.

Related Material