线性有界自动机

线性有界自动机是一种多轨迹非确定性图灵机，其磁带具有一定有界有限长度。

长度 = 函数（初始输入字符串的长度，常数 c）

这里，

内存信息 ≤ c × 输入信息

计算限制在常数有界区域内。输入字母表包含两个特殊符号，用作左端标记和右端标记，这意味着转换既不会移动到左端标记的左侧，也不会移动到磁带的右端标记的右侧。

线性有界自动机可以定义为一个 8 元组 (Q, X, ∑, q₀, ML, MR, δ, F)，其中 -

• Q 是一个有限的状态集

• X 是磁带字母表

• ∑ 是输入字母表

• q₀ 是初始状态

• M_L 是左端标记

• M_R 是右端标记，其中 M_R ≠ M_L

• δ 是一个转移函数，它将每个 (状态，磁带符号) 对映射到 (状态，磁带符号，常数 'c')，其中 c 可以是 0 或 +1 或 -1

• F 是最终状态集

确定性线性有界自动机总是上下文敏感的，而具有空语言的线性有界自动机是不可判定的。