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

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

作　　者：张雪峰[1] 许丽娟[1] 罗洪霞[1] 党德玉[2] 

机构地区：[1]广东工业大学华立学院,广东广州511325 [2]东北电力大学信息工程学院,吉林吉林132012

出　　处：《计算机与现代化》2008年第6期4-7,共4页Computer and Modernization

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

关 键 词：上下文无关文法 递归推导 文法构造 文法推断 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]