Simple DFA Are Polynomially Probably Exactly Learnable from Simple Examples

Abstract

Efficient learning of DFA is a challenging research problem in grammatical inference. Both exact and approximate (in the PAC sense) identi ability of DFA from examples is known to be hard. Pitt, in his seminal paper posed the following open research problem: "Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?" (Pitt, 1989). We demonstrate that the class of simple DFA (i.e., DFA whose canonical representations have logarithmic Kolmogorov complexity) is efficiently probably exactly learnable under the Solomono Levin universal distribution m (wherein an instance x with Kolmogorov complexity K(x) issampled with probability that is proportional to 2;K(x)). The simple distribution independent learning theorem states that a concept class is learnable under the universal distribution m i it is learnable under the entire class of simple distributions provided the examples are drawn according to the universal distribution (Li & Vitanyi, 1991). The class of simple distributions includes all computable distributions. Thus, it follows that the class of simple DFA is learnable under a sufficiently general class of distributions.