線形拘束オートマトン
(Linear bounded automaton から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/01 15:10 UTC 版)
線形拘束オートマトン(せんけいこうそくオートマトン、英: linear bounded automaton, LBA)は、制限されたチューリングマシンである。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する(つまり一次関数である)。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。
- 1 線形拘束オートマトンとは
- 2 線形拘束オートマトンの概要
線形拘束オートマトンと同じ種類の言葉
- 線形拘束オートマトンのページへのリンク