A general approach to inference of context-free programmed grammars

摘要

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