令和6年度 III-4

解説

この問題で問われていること

プッシュダウン・オートマトンとチューリング機械に関する5つの記述のうち、最も適切なものを選ぶ問題。

解き方

① プッシュダウン・オートマトン=有限オートマトン+スタック。認識できるのは文脈自由言語(すべて)。非決定性は決定性より強い。チューリング機械のテープは無限長。停止性問題は判定できない
② ①「認識できないものがある」、②「すべて決定性にできる」、④「停止を判定できる」、⑤「有限長のテープ」が誤り
③ ③

正解が正しい理由

プッシュダウン・オートマトンは、有限オートマトンに、スタック(後入れ先出しの記憶)と、スタックに関する操作(プッシュ、ポップ)を加えたものである。したがって③が最も適切である。

各選択肢について

• ① プッシュダウン・オートマトンが認識できる言語は文脈自由言語で、文脈自由言語は全て認識できる(両者は等価)ため、「認識できないものがある」は誤り。
• ② 非決定性プッシュダウン・オートマトンは、決定性プッシュダウン・オートマトンより認識能力が高く、全てが等価な決定性のものを持つわけではない。
• ③ プッシュダウン・オートマトンは、有限オートマトンにスタックと、スタックに関する操作を加えたもので、これが正答。
• ④ 任意のチューリング機械と入力について、停止するか否かを判定するチューリング機械は構成できない(停止性問題は決定不能)。
• ⑤ チューリング機械のテープは、有限長ではなく、両方向に無限長である。

覚えるべきポイント

有限オートマトンは正規言語、プッシュダウン・オートマトンは文脈自由言語、チューリング機械は帰納的可算言語を扱う。停止性問題は決定不能。非決定性PDAは決定性PDAより強力。