非決定性プッシュダウンオートマトンが受理する言語のクラスと等しいものはどれか。

解説

正解は「文脈自由文法が生成する言語のクラス」です。任意の文脈自由文法に対して、スタック上で最左導出を模倣する非決定性プッシュダウンオートマトンを作れます。スタックの先頭が非終端記号なら規則の右辺に置き換え、終端記号なら入力と照合して取り除きます。逆に、任意の非決定性プッシュダウンオートマトンから、同じ言語を生成する文脈自由文法も作れます。「正規文法が生成する言語のクラス」は有限オートマトンが受理するクラスで、真に小さくなります。「文脈依存文法が生成する言語のクラス」は線形有界オートマトンに対応し、真に大きくなります。「決定性有限オートマトンが受理する言語のクラス」も正規言語のクラスです。