文脈依存文法が生成する言語のクラスと、受理する言語のクラスが等しい計算モデルはどれか。

解説

正解は「線形有界オートマトン」です。線形有界オートマトンは、テープのうち入力が書かれた範囲（入力の長さに比例する範囲）しか使えない非決定性チューリング機械です。文脈依存文法の規則は右辺が左辺より短くならないため、導出途中の記号列は最終的な記号列より長くならず、入力の長さ程度の領域で模倣できます。「非決定性プッシュダウンオートマトン」は文脈自由言語に、「決定性有限オートマトン」は正規言語に対応し、いずれも真に小さいクラスです。「2本のスタックをもつプッシュダウンオートマトン」は、2本のスタックでテープの左右を表せるためチューリング機械と同等で、より大きな帰納的可算言語のクラスを受理します。