Learning Probabilistic Languages by k-Testable Machines

A k-testable machine is a finite automaton which recognizes a language L by only seeing a window of size k of each string in L. In this paper we use k-testable machines to recognize probabilistic languages and propose a novel algorithm to learn them. We work in the context of passive learning as our algorithm is based on a finite sample of strings belonging to the target language equipped with frequencies. Because our algorithm learns a probabilistic automaton, the resulting language is less sensitive to noise threshold than Garcia's algorithm. When compared with the ALERCIA learning algorithm, our method provides a better result in the case of the target language being a k-testable language. In fact, in this case, for the given window k we can learn at the limit the target language exactly.