查看“︁用户:LynChern/Sandbox”︁的源代码

一个'''线性有界自动机'''（LBA）是一种抽象机器，它与[[Turing machine|图灵机]]相同，除了在给定输入的计算期间，其磁带头不允许移动到其无限磁带的有界区域之外，可访问的磁带单元数量是输入大小的线性函数。磁带本身具有无限长度以适应任意长度的输入。（这种模型的一个等效替代版本为LBA提供不同长度的有限磁带，每个不同大小的输入对应一个磁带，磁带的长度是输入大小的线性函数。在这个替代版本中，有无限多个有限磁带的供应，每个输入大小对应一个磁带。）

与图灵机类似，LBA是一个配备磁带的[[finite state machine|有限状态机]]。与图灵机系统不同，LBA系统（有限状态机加上其磁带）对于每个输入只有有限多个系统状态；也就是说，对于每个输入，LBA系统表现得像一个有限自动机。LBA和有限状态自动机（FSA）之间的一个相关区别是，FSA的状态数量对于该FSA是固定的，而LBA的状态数量随给定输入量的线性函数变化。

使用泵引理可以证明，存在一些语言，它们被某些LBA识别，但无法被任何[[push-down automaton|下推自动机]]识别。线性有界自动机识别[[context-sensitive language|上下文有关语言]]类。

==历史==
Myhill (1960) 引入了LBA，其动机是Rabin和Scott (1959) 对有限自动机的研究。

==另见==
* [[:Category:Linear bounded automata|线性有界自动机分类]]（本维基中具有与LBA等效能力的语言列表）

==外部资源==
* [[Wikipedia:Linear bounded automaton|维基百科：线性有界自动机]]

[[Category: Computational models]]