线性有界自动机

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

參考文獻[编辑]

  • 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)

外部链接[编辑]