計算モデルと、それがもつ補助記憶の組合せとして、正しいものはどれか。

解説

正解は「プッシュダウンオートマトン ― スタック」です。プッシュダウンオートマトンは、有限オートマトンにスタックを1本加えた計算モデルで、スタックに記号を積んだり取り出したりしながら入力を読むため、$a^n{b}^n$ のように個数を照合する言語も受理できます。「有限オートマトン ― キュー」は誤りで、有限オートマトンは補助記憶をもたず、状態だけで情報を覚えます。「チューリング機械 ― スタック」も誤りで、チューリング機械は読み書きできる無限長のテープをもち、ヘッドを左右に動かせます。「プッシュダウンオートマトン ― 読み書きできる無限長のテープ」はチューリング機械の説明です。スタックやテープの大きさは、有限とは限りません。