线性有界自动机

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

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

识别

时，先扫描一次检查输入形如 $a^{+}{b}^{+}{c}^{+}$，再反复寻找最左侧未标记的 $a$，把它标为 $A$；随后向右分别找到第一个未标记的 $b,c$，改为 $B,C$，再回到左端。若某段提前耗尽便拒绝；没有未标记 $a$ 时，还要检查所有 $b,c$ 都已标记。

例如每轮结束时，带内容依次为 $aabbcc\to AaBbCc\to AABBCC$，于是接受。对 aabbc，第一轮得到 AaBbC，第二轮虽然能找到余下的 a,b，却找不到 c，因此拒绝。形状预检不可省略，否则只配对数量可能误收次序不对的串。

为避免混淆，把输入总长度写作 $N$：在成员输入 $a^n{b}^n{c}^n$ 上 $N=3n$。所有标记都写回原有 $N$ 个带格，不新增长串；每轮至多扫描 $O(N)$ 格，共 $O(N)$ 轮，所以这个具体算法用 $O(N)$ 空间和 $O(N^2)$ 时间。

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

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

LBA 接受语言与上下文有关语言理路上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。在语言类层面等价，前提是双方统一空字约定：若文法允许受控的 $S\to \epsilon$，机器也单独处理空输入。双向构造由专门定理页承担。

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