Inference of regular grammars via skeletons

A constructive method for the inference of regular grammars from positive sample strings of language using skeletal structure descriptions, is proposed, and polynomial-time algorithms based on the method are presented. The algorithms infer in the limit a class of regular languages, designated as terminal distinguishable regular languages. They do not overgeneralize if the samples are from a certain class of context-free languages capturing one of these basic results in formal language theory. The algorithms are adaptable for online inference. A measure of goodness for constructive methods for the problem of grammatical inference is introduced. Several examples are given to show the working and behavior of the algorithms.