|
|||||
|
|
| 袋自动机 | |
| 引用本文： | 张继军,吴哲辉,董卫,耿霞.袋自动机[J].计算机研究与发展,2008,45(Z1):190-195. |
| 作者姓名： | 张继军 吴哲辉 董卫 耿霞 |
| 作者单位： | 1. 山东农业大学信息学院,泰安,271018 2. 山东科技大学信息学院,青岛,266510 3. 山东农业大学信息学院,泰安,271018;山东科技大学信息学院,青岛,266510 |
| 摘 要： | 提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图;分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性;研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言. |
| 关 键 词： | 袋自动机 状态转换图 袋语言 重复序列 |
| 修稿时间： | 2007年7月10日 |
Bag Automata |
|
| Zhang Jijun,Wu Zhehui,Dong Wei,Geng Xia.Bag Automata[J].Journal of Computer Research and Development,2008,45(Z1):190-195. | |
| Authors: | Zhang Jijun Wu Zhehui Dong Wei Geng Xia |
| Affiliation: | Zhang Jijun1,Wu Zhehui2,Dong Wei1,, Geng Xia1,21(College of Information,Sh,ong Agriculture University,Tai'an 271018)2(College of Information,Sh,ong University of Science , Technology,Qingdao 266510) |
| Abstract: | 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 g... |
| Keywords: | bag automata state transition diagram bag language repetitive sequence |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |