线性有界自动机

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

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

这里，

内存信息≤c×输入信息

计算仅限于恒定有界区域。输入字母表包含两个特殊符号，用作左端标记和右端标记，这意味着过渡既不会移动到磁带左端标记的左侧，也不会移动到磁带右端标记的右侧。

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

  • Q是有限状态集

  • X是磁带字母表

  • Σ是输入字母表

  • q 0是初始状态

  • M L是左端标记

  • M R是右端标记，其中 M R ≠ M L

  • δ是一个转换函数，它将每对（状态、磁带符号）映射到（状态、磁带符号、常量“c”），其中 c 可以是 0 或 +1 或 -1

  • F是最终状态的集合

线性有界自动机

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