线性有界自动机
维基百科，自由的百科全书
线性有界自动机(简写 LBA)是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它不同于图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。
线性有界自动机是上下文有关语言的接受器。对这种语言在文法上的唯一限制是没有把字符串映射成更短字符串的产生式。所以在上下文有关语言中没有字符串的推导可以包含比字符串自身更长的句子形式。因为在线性有界自动机和这种文法之间的一一对应，对于要被自动机识别的字符串不需要比原始字符串所占用的更多的磁带。
[编辑] 外部链接
- Linear Bounded Automata by Forbes D. Lewis
- Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
- Linear-Bounded Automata , part of Theory of Computation syllabus, by David Matuszek
| 自动机理论: 形式语言和形式文法 | |||
|---|---|---|---|
| 乔姆斯基层级 | 文法 | 语言 | 极小自动机 |
| 类型 0 | 无限制 | 递归可枚举 | 图灵机 |
| n/a | (无公用名) | 递归 | 判定器 |
| 类型 1 | 上下文有关 | 上下文有关 | 线性有界 |
| n/a | 附标 | 附标 | 嵌套堆栈 |
| n/a | 树-邻接 | 适度上下文有关 | 嵌入下推 |
| 类型 2 | 上下文无关 | 上下文无关 | 非确定下推 |
| n/a | 确定上下文无关 | 确定上下文无关 | 确定下推 |
| 类型 3 | 正则 | 正则 | 有限 |
| 每个语言或文法范畴都是其直接上面的范畴的真子集。 | |||
