線性有界自動機

線性有界自動機是一種圖靈機，是把計算限制在僅僅包含輸入的那一段帶上的圖靈機。可用作上下文有關語言的識別接受器。

線性有界自動機（縮寫為LBA）可形式地由

來表示。其中：K 是狀態的有限集；Γ 是帶符號的有限集；

是輸人符號集；K 中的 q₀是起始狀態；

是終結狀態集；δ 是從

到

子集的映射，(L,R)分別是讀寫頭左右移一格。Σ含有兩個特殊的符號，通常記為 Ȼ 和 $ ，它們分別是左端標誌和右端標誌。這些符號開始就處在輸入帶的端點，其作用是阻止帶頭離開帶上出現符號的區。

確定型和非確定型圖靈機接受的語言是相同的。

非確定型線性有界自動機（以 NDLBA 表示）接受的語言類正好是上下文有關語言。

確定型線性有界自動機（以DLBA 表示）的功能不會超過 NDLBA 的，以不等式表示為

其中 L 表示該類自動機接受的語言集合。至今人們仍未能把包含關係精確為真包含關係或相等關係。這是一個著名的尚未解決的問題，簡稱 LBA 問題。 ^[1] 

圖靈機，又稱圖靈計算、圖靈計算機，是由數學家阿蘭·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人們進行數學運算。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。