基本情報技術者 予想問題｜A 第20問

解説

プッシュダウンオートマトンは有限オートマトンにスタックを追加した計算モデルであり、受理できる言語クラスは文脈自由言語である。よってイが正解である。スタックにより括弧の対応のような入れ子構造を記憶できるため、プログラミング言語の構文解析の理論的基盤となっている。アの正規言語はスタックを持たない有限オートマトンで受理でき、正規表現と等価な最も単純なクラスである。ウの文脈依存言語は線形拘束オートマトン、エの帰納的可算言語はチューリングマシンがそれぞれ対応する。チョムスキー階層における「正規言語＝有限オートマトン」「文脈自由言語＝プッシュダウンオートマトン」という言語クラスと計算モデルの対応関係は頻出の暗記事項である。