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