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