平成30年度 III-3

解説

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

オートマトンの種類と、その計算能力、計算可能性(停止性問題)についての基本を確認する問題。

解き方

① オートマトンの階層: 有限オートマトン+スタック=プッシュダウン・オートマトン(文脈自由言語をちょうど認識)、テープを無限長にするとチューリング機械。停止するかどうかを判定する機械は作れない
② ①非決定性は決定性に直せない場合がある、②テープは無限長、③停止性は判定できない、④認識できない文脈自由言語はない
③ ⑤

正解が正しい理由

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

各選択肢について

• ① 非決定性プッシュダウン・オートマトンは、決定性のものより認識能力が高く、等価な決定性プッシュダウン・オートマトンを持たない場合がある(決定性は、決定性文脈自由言語のみ認識)。
• ② チューリング機械は、スタックの代わりに、無限長のテープを持つ。有限長のテープではない。
• ③ 任意のチューリング機械Mと入力σに対して、Mが停止するかどうかを判定するチューリング機械は、存在しない(停止性問題は決定不能)。
• ④ プッシュダウン・オートマトンが認識できる言語のクラスは、文脈自由言語のクラスと一致する。プッシュダウン・オートマトンで認識できない文脈自由言語は存在しない。
• ⑤ プッシュダウン・オートマトンは、有限オートマトンに、スタックとスタックに関する操作を加えたもの。これが正答。

覚えるべきポイント

有限オートマトン(正規言語)<プッシュダウン・オートマトン(文脈自由言語)<線形拘束オートマトン(文脈依存言語)<チューリング機械(帰納的可算言語)。停止性問題は決定不能。