線性有界自動機

線性有界自動機（英文：Linear bounded automaton，簡寫： LBA）是受限形式的非確定圖靈機。它擁有由包含來自有限字母表的符號的單元構成的磁帶，可以一次讀取和寫入磁帶上一個單元的並可以移動的磁頭，和有限數目個狀態。它區別於更為普遍的圖靈機在於儘管磁帶最初被認為是無限的，只有其長度是初始輸入的線性函數的有限臨近部分可以被讀寫磁頭訪問。這個限制使 LBA 成為在某些方面比圖靈機更接近實際存在的計算機的精確模型。

結構

線性有界自動機是一個非確定型圖靈機，並遵循以下三個條件：

• 其輸入字母表中包括兩個特殊符號「[」「]」，作為左右端點的標記。
• 左右端點標記所在的單元不能被重寫。
• 讀寫頭不能移動到左端點的左邊或右端點的右邊。

也就是說，雖然線性有界自動機如其他圖靈機一樣擁有一條無限長的帶，但是帶上能夠使用的部分是有限的：介於左右端點之間。

語言

線性有界自動機是上下文有關語言的接受器。對這種語言在文法上的唯一限制是沒有把字符串映射成更短字符串的產生式。所以在上下文有關語言中沒有字符串的推導可以包含比字符串自身更長的句子形式。因為在線性有界自動機和這種文法之間的一一對應，對於要被自動機識別的字符串不需要比原始字符串所占用的更多的磁帶。

線性有界自動機問題

在1964年的一篇論文中，S.Y.Kuroda（黒田成幸） 提出了兩個問題，即著名的「LBA Problem」：

1. 線性有界自動機接受的語言是否與確定型線性有界自動機接受的語言等價？
2. 能被線性有界自動機接受的語言是否在補運算下具有封閉性？

在這篇論文中，Kuroda表示，若問題2的答案是否定的，則問題1的答案也是否定的。然而，在1987年，N.Immerman 與 R.Szelepcsényi 證明了問題2的答案是肯定的。至今，問題1仍然沒有被證明或證偽。

定理

• 波斯特定理
• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理

參考文獻

• John Myhill: Linearly Bounded Automata, WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
• Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control 6(2): 131-136 (1963)
• Sige-Yuki Kuroda: Classes of languages and linear-bounded automata, Information and Control, 7(2): 207–223 (1964)

外部連結

• Linear Bounded Automata by Forbes D. Lewis
• Linear Bounded Automata （頁面存檔備份，存於網際網路檔案館） slides, part of Context-sensitive Languages （頁面存檔備份，存於網際網路檔案館） by Arthur C. Fleck （頁面存檔備份，存於網際網路檔案館）
• Linear-Bounded Automata （頁面存檔備份，存於網際網路檔案館） , part of Theory of Computation syllabus, by David Matuszek