線形拘束オートマトン
線形拘束オートマトンは、いくつかの有界有限長のテープを備えたマルチトラック非決定性チューリングマシンです。
Length = function (Length of the initial input string, constant c)
ここに、
Memory information ≤ c × Input information
計算は、一定の境界領域に制限されます。入力アルファベットには、左端マーカーと右端マーカーとして機能する2つの特別な記号が含まれています。これは、トランジションがテープの左端マーカーの左側にも右端マーカーの右側にも移動しないことを意味します。
線形拘束オートマトンは、8タプル(Q、X、∑、q 0、ML、MR、δ、F)として定義できます。
Q 状態の有限集合です
X テープアルファベットです
∑ 入力アルファベットです
q0 初期状態です
ML 左端のマーカーです
MRM右端マーカーでR ≠M Lは
δ は、各ペア(状態、テープシンボル)を(状態、テープシンボル、定数 'c')にマップする遷移関数です。ここで、cは0または+1または-1になります。
F 最終状態のセットです

決定論的線形拘束オートマトンは常に context-sensitive そして、空の言語を持つ線形拘束オートマトンは undecidable.。