2018年10月23日

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

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

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



【正解】 D

@非決定性プッシュダウン・オートマトン ⊂ 決定性プッシュダウン・オートマトン
 の関係があり、全ての非決定性プッシュダウン・オートマトンは、等価な
 決定性プッシュダウン・オートマトンに変換が可能である。
 本質的には適切な記述であると考えられる。
Aチューリング機械は、プッシュダウン・オートマトンのスタックを
 無限長のテープに代えたものである。
B必ずしも万能チューリング機械を構成できるわけではない。
Cプッシュダウン・オートマトンが認識できる言語と文脈自由言語は
 等価な関係がある。
D正しい。

EXCELのマクロのご相談なら  ファーストマクロ  



posted by ファーストマクロ at 00:21| Comment(0) | H30技術士一次試験(情報工学)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: