線形拘束オートマトン

線形拘束オートマトン（せんけいこうそくオートマトン、）は、制限されたチューリングマシンである。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。

線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存文法によって生成される文字列のいかなる導出も、その文字列自身よりも長い文字列を経由することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。

 外部リンク 
 Linear Bounded Automata by Forbes D. Lewis
 Linear-Bounded Automata , part of Theory of Computation syllabus, by David Matuszek
 線形拘束オートマトンを用いた組込みソフトウェアの仕様記述に関する考察、二口祐介（他）、南山大学

Category:オートマトン
Category:計算モデル
Category:数学に関する記事