プッシュダウンオートマトンの受理の方式には「最終状態で受理」と「空スタックで受理」がある。非決定性プッシュダウンオートマトンについて、両者の関係として正しいものはどれか。

解説

正解は「どちらの方式でも、受理できる言語のクラスは等しい」です。最終状態で受理する NPDA は、受理状態に達したらスタックを空にする動作を加えると、空スタックで受理する NPDA に変換できます。逆に、スタックの底に特別な記号を置き、それが現れたときに受理状態へ移る動作を加えれば、空スタックで受理する NPDA を最終状態で受理するものに変換できます。どちらも文脈自由言語のクラスを受理します。「空スタックで受理する方式の方が、…大きい」と「最終状態で受理する方式の方が、…大きい」は誤りです。「空スタックで受理する方式では、正規言語しか受理できない」も誤りです。