二元文法

摘要：

在正规文法的基础上,通过增加一个约束变量集合,给出了二元文法的定义,证明了二元文法与袋自动机的等价性,定义了平衡推导、递增推导、递减推导和传递推导,证明了它们与不变重复序列、增重复序列、减重复序列和传递重复序列之间的关系,并且给出判定一个二元文法所产生语言(袋语言)分别是正规语言、上下文无关语言或上下文有关语言的充分条件.

关键词： 二元文法 袋自动机 袋语言

作者: 张继军 费玉奎 董卫

作者单位: 山东农业大学信息学院,山东,泰安,271018

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 95-97,117

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）