A general approach to inference of context-free programmed grammars

A general approach to the inference of context-free programmed grammars (CFPG) is proposed on the basis of inferability analysis. The method is applicable to a sufficiently large class of languages to be used for string pattern description in syntactic pattern recognition. Languages with basic recursive structure whose recursive parameter can be represented by polynomial functions with finite terms are always suitable for the suggested method. Five major problems are discussed: sample set generalization, string segmentation, CFPG trunk grammar inference, CFPG subgrammar inference, and derivation program unification.