线性有界自动机

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

长度 = 函数 (初始输入字符串的长度，常数 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 是最终状态的集合

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