線形拘束オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/19 04:12 UTC 版)
線形拘束オートマトン（せんけいこうそくオートマトン、英: linear bounded automaton, LBA）は、制限されたチューリングマシンである。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。
線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存文法によって生成される文字列のいかなる導出も、その文字列自身よりも長い文字列を経由することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。
外部リンク
- Linear Bounded Automata by Forbes D. Lewis
- Linear-Bounded Automata , part of Theory of Computation syllabus, by David Matuszek
- 線形拘束オートマトンを用いた組込みソフトウェアの仕様記述に関する考察、二口祐介（他）、南山大学
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
線形拘束オートマトンと同じ種類の言葉
- 線形拘束オートマトンのページへのリンク
