袋自动机

摘要：

提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图；分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性；研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言.

关键词： 袋自动机 状态转换图 袋语言 重复序列 真子集

作者: 张继军 吴哲辉 董卫 耿霞

作者单位: 山东农业大学信息学院,泰安,271018 山东科技大学信息学院,青岛,266510 山东农业大学信息学院,泰安,271018;山东科技大学信息学院,青岛,266510

会议类型: 国内会议

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

会议地点: 南宁

会议语种:中文

页码: 190-195

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