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