Inference of a subclass of context free grammars using positive samples
J. A. Laxminarayana, G. S. Nagaraja · 2003
It is known that family of context-free languages is not identifiable in the limit from positive data. However, it is known that some useful subclasses of context-free languages are identifiable in the limit. In this work we introduce a new subclass of context-free languages, Terminal Distinguishable Context Free Languages (TDCFL) through a grammatical characterization. The Griebach Normal Form representation is used to represent the rewriting rules of underlying grammar of TDCFL and terminal distinguishability property is employed to merge contextual entities. A polynomial time algorithm is proposed to identify a TDCFL and it is shown that the algorithm correctly identifies any TDCFL in the limit if enough positive samples are given.