線形拘束オートマトン
線形拘束オートマトン（せんけいこうそくオートマトン、英: 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
- 線形拘束オートマトンを用いた組込みソフトウェアの仕様記述に関する考察、二口祐介（他）、南山大学