Automata Theory 简明教程
Linear Bounded Automata
线性有界自动机是一个多轨非确定性图灵机，其磁带具有某种有界有限长度。
Length = function (Length of the initial input string, constant c)
在此，
Memory information ≤ c × Input information
计算受限于常量有界区域。输入字母表包含两个特殊符号，用作左端标记和右端标记，这意味着转换既不会移动到左端标记的左边，也不会移动到磁带右端标记的右边。
线性有界自动机可以定义为 8 元组 (Q, X, ∑, q0, ML, MR, δ, F)，其中 −
-
Q 是有限状态集
-
X 是磁带字母表
-
∑ 是输入字母表
-
q0 是初始状态
-
ML 是左端标记
-
MR 是右端标记，其中 MR ≠ ML
-
δ 是转换函数，它将每对 (状态、磁带符号) 映射到 (状态、磁带符号、常数‘c’)，其中 c 可以是 0 或 +1 或 -1
-
F 是结束状态的集合
确定性线性有界自动机总是 context-sensitive ，而空语言线性有界自动机是 undecidable. 。