プッシュダウン・オートマトンとチューリング機械に関する次の記述の
うち、最も適切なものはどれか。
① 全ての非決定性プッシュダウン・オートマトンは、等価な
決定性プッシュダウン・オートマトンを持つ。
② チューリング機械は、プッシュダウン・オートマトンのスタックを
有限長のテープに代えたものであり、スタックに関する操作の
代わりにテープ上の書き込み位置を左右に動かす操作が
加えられている。
③ 任意のチューリング機械Ｍと任意の記号列σに対して、
Ｍがσを入力として行う計算が停止するか否かを判定する
万能チューリング機械を必ず構成できる。
④ プッシュダウン・オートマトンが認識できる言語は文脈自由で
あるが、文脈自由言語の中には、プッシュダウン・オートマトンで
認識できないものがある。
⑤ プッシュダウン・オートマトンは、 有限オートマトンに対してスタック
とスタックに関する操作を加えたものである。
①非決定性プッシュダウン・オートマトン ⊂ 決定性プッシュダウン・オートマトン
の関係があり、全ての非決定性プッシュダウン・オートマトンは、等価な
決定性プッシュダウン・オートマトンに変換が可能である。
本質的には適切な記述であると考えられる。
②チューリング機械は、プッシュダウン・オートマトンのスタックを
無限長のテープに代えたものである。
③必ずしも万能チューリング機械を構成できるわけではない。
④プッシュダウン・オートマトンが認識できる言語と文脈自由言語は
等価な関係がある。
⑤正しい。
EXCELのマクロのご相談なら ファーストマクロ へ
タグ：チューリング機械
