一个上下文无关文法的构造定理及其在推断中的应用

A Constructing Theorem of Context-free Grammar and Application in Grammatical Inference

递归概念可以在句子中重复派生、循环出现。对这样的句子推断时,若为递归概念的每一个派生部分引进一个递归概念来描述,将推断出多个与之有相似的产生式结构的递归概念,同时也构造出一个新文法。本文先给出新文法的形式化构造方法,证明了新文法与原文法的等价性。在文章的后部,通过实例,介绍该定理在简化复杂文法推断中的应用。

The paper uses several concepts to express the different segments, the recursion can repeatedly derive and revolve, there derive new grammars through recursion which is provided with the similar production set. So it can get many concepts which has a similar structure to the old concept. At the same time there also get a new grammar which owns the new concepts. At first, the paper gives the formal definition for the method to construct a new grammar mentioned above and has proved the equivalence of two grammars, then it introduces the application in predigesting the complicated grammatical inference by samples.