袋自动机  

Bag Automata

作　　者：张继军[1] 吴哲辉[2] 董卫[1] 耿霞[1,2] 

机构地区：[1]山东农业大学信息学院,泰安271018 [2]山东科技大学信息学院,青岛266510

出　　处：《计算机研究与发展》2008年第z1期190-195,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60673053)

摘　　要：提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图;分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性;研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言.The concept of bag automata and of bag language is presented, the state transition diagram of bag automata is given in this paper, the relation between bag language and the languages in Chomsky hierarchy is studied. It is proofed that the class of bag language is a subclass of context-sensitive language, the class of regular language is a subclass of the class of bag language, the class of bag language is not a subclass of context-free language and vice versa. The structural properties of bag language are given by analyzing the repetitive sequence of bag language in the state transition diagram of bag automata.

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

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]