INFERENCE OF KAPPA-TESTABLE LANGUAGES IN THE STRICT SENSE AND APPLICATION TO SYNTACTIC PATTERN-RECOGNITION

The inductive inference of any language from the (general) class of regular languages, from only positive samples of this language, is well known to be an undecidable problem. However, it has fortunately been shown that this is not the case for certain particular subclasses of languages. This correspondence is concerned with the inductive inference of one of these classes, namely, the class of k-testable languages in the strict sense (k-TSSL). A k-TSSL is essentially defined by a finite set of substrings of length k that are permitted to appear in the strings of the language. Given a positive sample R of strings of an unknown language, we obtain a deterministic finite-state automaton that recognizes the smallest k-TSSL containing R. The inferred automaton is shown to have a number of transitions bounded by O(m) where m is the number of substrings defining this k-TSSL, and the inference algorithm works in O(kn log m) where n is the sum of the lengths of all the strings in R. The proposed methods are illustrated through syntactic pattern recognition experiments in which a number of strings generated by ten given (source) non-k-TSSL grammars are used to infer ten k-TSSL stochastic automata, which are further used to classify new strings generated by the same source grammars. The results of these experiments are consistent with the theory, showing as well the ability of (stochastic) k-TSSL’s to approach other classes of regular languages. © 1990, IEEE.