2018年10月23日

平成30年度 技術士第一次試験問題 情報工学部門 V−3

V−3
プッシュダウン・オートマトンとチューリング機械に関する次の記述の
うち、最も適切なものはどれか。

 @ 全ての非決定性プッシュダウン・オートマトンは、等価な
   決定性プッシュダウン・オートマトンを持つ。
 A チューリング機械は、プッシュダウン・オートマトンのスタックを
   有限長のテープに代えたものであり、スタックに関する操作の
   代わりにテープ上の書き込み位置を左右に動かす操作が
   加えられている。
 B 任意のチューリング機械Mと任意の記号列σに対して、
   Mがσを入力として行う計算が停止するか否かを判定する
   万能チューリング機械を必ず構成できる。
 C プッシュダウン・オートマトンが認識できる言語は文脈自由で
   あるが、文脈自由言語の中には、プッシュダウン・オートマトンで
   認識できないものがある。
 D プッシュダウン・オートマトンは、 有限オートマトンに対してスタック
   とスタックに関する操作を加えたものである。



答えはこちら
posted by ファーストマクロ at 00:21| Comment(0) | H30技術士一次試験(情報工学)