Automata-theory-linear-bounded-automata
提供：Dev Guides
線形有界オートマトン
線形有界オートマトンは、有界有限長のテープを備えたマルチトラック非決定性チューリングマシンです。
長さ=関数（初期入力文字列の長さ、定数c）
ここに、
メモリ情報≤c×入力情報
計算は、一定の境界領域に制限されます。 入力アルファベットには、テープの左端マーカーの左にも右端マーカーの右にも移動しないことを意味する、左端マーカーと右端マーカーとして機能する2つの特殊記号が含まれています。
線形有界オートマトンは、8タプル（Q、X、∑、q〜0〜、ML、MR、δ、F）として定義できます。ここで、
- Q は状態の有限集合です
- X はテープのアルファベットです
- ∑ は入力アルファベットです
- * q〜0〜*は初期状態です
- * M〜L〜*は左端のマーカーです
- * M〜R〜*は右端マーカーで、M〜R〜≠M〜L〜
- *δ*は遷移関数で、各ペア（状態、テープシンボル）を（状態、テープシンボル、定数「c」）にマッピングします。cは0または+1または-1です。
- F は最終状態のセットです
決定論的な線形有界オートマトンは常に*コンテキスト依存*であり、空の言語を持つ線形有界オートマトンは*決定不能*です。
