決定性プッシュダウンオートマトン（DPDA）と非決定性プッシュダウンオートマトン（NPDA）について、正しい記述はどれか。

解説

正解は「DPDA が受理する言語のクラスは、NPDA が受理する言語のクラスの真部分集合である」です。有限オートマトンでは決定性と非決定性の能力が等しいのに対し、プッシュダウンオートマトンでは差が生じます。例えば偶数長の回文の言語は、どこが文字列の中央かを読みながら判断できないため、中央を非決定的に推測する NPDA でなければ受理できません。DPDA が受理する言語は決定性文脈自由言語と呼ばれ、構文解析の基礎になります。「両者が受理する言語のクラスは等しい」と「DPDA の方が、受理できる言語のクラスが大きい」は誤りです。「NPDA は空動作を使えないが、DPDA は使える」も誤りで、どちらも空動作を使えます。