线性有界自动机

形式陈述 ​

线性有界自动机（LBA）是一台非确定性图灵机公理库非确定性图灵机Nondeterministic Turing machine每个配置可有多个后继并在存在接受分支时接受的图灵机。，在长度为 $n$ 的输入上只能访问至多 $cn+c_0$ 个带格，其中常数 $c,c_0$ 与输入无关。常见的一带定义把输入置于两个不可越过的端标记之间，机器可在这段区域内读写，但不得移出；允许多带或额外常数倍工作区会得到同一语言类。

对输入 $w$，只要存在一条有限计算分支进入接受状态，LBA 就接受 $w$。识别语言时，非成员输入可以没有接受分支；由于固定输入长度下可能配置数有限，可把重复配置视为无用循环，并把模型正规化为总会停机的非确定性判定过程。这里“线性有界”约束的是空间，而不是时间。

直觉 ​

LBA 从非确定性图灵机公理库非确定性图灵机Nondeterministic Turing machine每个配置可有多个后继并在存在接受分支时接受的图灵机。直接继承双向移动、原地改写与存在分支接受语义，却不给它无限扩展工作带；普通图灵机模型由这一直接前置传递提供，无需并列重复。输入越长，可用记忆按比例增长，因此它比只有有限状态或单栈的模型更能协调多个远距离约束；但它无法随计算任意申请新空间。

端标记把空间预算变成可见的物理边界。机器可以把已处理符号改成带标记版本，反复扫描输入，在不复制整个输入到额外区域的情况下维护进度。这种“在原输入上做有限标注”的图像解释了许多上下文有关语言算法。

例子与边界 ​

识别

$$\{a^n{b}^n{c}^n:n\ge 1\}$$

时，LBA 可反复寻找最左侧未标记的 $a$，把它标为 $A$；随后向右标记一个未处理的 $b$ 和一个未处理的 $c$。若顺序不符、某段提前耗尽或最后仍有未标记符号便拒绝。所有标记都写回原有 $n$ 个带格，空间为 $O(n)$，而多轮扫描允许时间达到多项式甚至更高。

线性空间绝不推出线性时间。机器可在有限配置图中长时间游走；空间限制只界定可写信息量。非确定性也不是随机选择：接受语义是存在一条接受分支，而不是接受概率为正。

经典 CSL–LBA 等价公理库CSL–LBA 等价定理CSL-LBA equivalence · Kuroda theorem上下文有关语言恰为非确定性线性有界自动机接受的语言。使用非确定性 LBA。确定性 LBA 是否识别同一语言类，等价于 $DSPACE(n)$ 与 $NSPACE(n)$ 是否相等的一个核心情形，仍不能当作已知事实。端标记、是否允许改写输入、一带或多带等约定可以互相模拟，但页面若改变模型，必须给出空间只增加常数倍的理由。

推论与应用 ​

LBA 接受语言与上下文有关语言公理库上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。的等价由专门定理页承担；本页只保留机器模型、空间界与非确定接受语义。

在空间复杂度公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。中，LBA 是线性空间机器的自动机版本。固定输入上的配置图大小至多指数级，因此可达性给出可判定过程；Immerman–Szelepcsényi 定理还推出非确定性线性空间对补封闭。LBA 由此连接文法层级与资源受限计算，而不是一种用于保证快速运行的工程模型。

参考资料

• Sige-Yuki Kuroda, “Classes of Languages and Linear-Bounded Automata,” Information and Control 7 (1964), 207–223.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, Ch. 11.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, Ch. 8, space complexity.