線性有界自動機

線性有界自動機是一種多軌跡非確定性圖靈機，其磁帶具有一定有界有限長度。

長度 = 函式（初始輸入字串的長度，常數 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 是最終狀態集

確定性線性有界自動機總是上下文敏感的，而具有空語言的線性有界自動機是不可判定的。