Inference of regular grammars via skeletons
- 1 November 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics
- Vol. 17 (6) , 982-992
- https://doi.org/10.1109/tsmc.1987.6499309
Abstract
A new constructive method for the inference of regular grammars from positive samples, using skeletal structure descriptions, is proposed and polynomial time algorithms based on the method are presented. The main results are 1) the proposed algorithms infer in the limit a class of regular languages, designated as terminal distinguishable regular languages (TDRL), 2) the algorithms do not overgeneralize if the samples are from a certain class of context-free languages capturing one of the basic results in formal language theory, and 3) the algorithms are adaptable for on-line inference. A new 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.Keywords
This publication has 0 references indexed in Scilit: