线性有界自动机

线性有界自动机（英文：Linear bounded automaton，简写： LBA）是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。

结构

线性有界自动机是一个非确定型图灵机，并遵循以下三个条件：

  • 其输入字母表中包括两个特殊符号“[”“]”，作为左右端点的标记。
  • 左右端点标记所在的单元不能被重写。
  • 读写头不能移动到左端点的左边或右端点的右边。

也就是说，虽然线性有界自动机如其他图灵机一样拥有一条无限长的带，但是带上能够使用的部分是有限的：介于左右端点之间。

语言

线性有界自动机是上下文有关语言的接受器。对这种语言在文法上的唯一限制是没有把字符串映射成更短字符串的产生式。所以在上下文有关语言中没有字符串的推导可以包含比字符串自身更长的句子形式。因为在线性有界自动机和这种文法之间的一一对应，对于要被自动机识别的字符串不需要比原始字符串所占用的更多的磁带。

线性有界自动机问题

在1964年的一篇论文中[1]，S.Y.Kuroda（黒田成幸） 提出了两个问题，即著名的“LBA Problem”：

  1. 线性有界自动机接受的语言是否与确定型线性有界自动机接受的语言等价？
  2. 能被线性有界自动机接受的语言是否在补运算下具有封闭性？

在这篇论文中，Kuroda表示，若问题2的答案是否定的，则问题1的答案也是否定的。然而，在1987年，N.Immerman 与 R.Szelepcsényi 证明了问题2的答案是肯定的。至今，问题1仍然没有被证明或证伪。

定理

参考文献

  • John Myhill: Linearly Bounded Automata, WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
  • Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control 6(2): 131-136 (1963)
  • Sige-Yuki Kuroda: Classes of languages and linear-bounded automata, Information and Control, 7(2): 207–223 (1964)

外部链接

  1. ^ S.-Y. Kuroda. Classes of Languages and Linear-Bounded Automata (PDF). 1964. [永久失效链接]