用户:LynChern/Sandbox

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

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

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