技術士第一次試験 専門科目情報工学部門 H30
通常
試験時間: 00:00問題時間: 00:00
問題一覧
問題 3 / 35
出典: 平成30年度技術士第一次試験問題[専門科目情報工学部門] III-3プッシュダウン・オートマトンとチューリング機械に関する次の記述のうち、最も適切なものはどれか。
①全ての非決定性プッシュダウン・オートマトンは、等価な決定性プッシュダウン・オートマトンを持つ。
②チューリング機械は、プッシュダウン・オートマトンのスタックを有限長のテープに代えたものである。
③任意のチューリング機械と記号列に対して、その計算が停止するか否かを判定する万能チューリング機械を必ず構成できる。
④プッシュダウン・オートマトンが認識できる言語は文脈自由であるが、文脈自由言語の中には認識できないものが存在する。
⑤プッシュダウン・オートマトンは、有限オートマトンにスタックとスタック操作を加えたものである。