ソフトウェア
プッシュダウンオートマトン（PDA）に関する説明として正しいものはどれか。
ア.PDAはチューリング機械と等価な計算能力を持ち、すべての計算可能な問題を解ける
イ.PDAは正規言語のみを認識でき、有限オートマトンとまったく同じ表現力をもつ
ウ.PDAはスタックをメモリとして利用することで、有限オートマトンでは認識できない文脈自由言語（例: aⁿbⁿ）を認識できる正解
エ.PDAはスタックの代わりにキューを使うことで文脈依存言語も認識できる
解説
PDAはDFAに「スタック」という無限のメモ帳を持たせたバージョン。このメモ帳のおかげでaⁿbⁿのような「数を数える」問題が解けるようになる！
なぜ ウ が正解か
プッシュダウンオートマトン（PDA）の特徴: ①有限制御部（有限オートマトン相当）＋スタックメモリで構成。②スタックにより文脈自由言語（CFL）を認識可能。例: aⁿbⁿ（aの数とbの数が等しい文字列）→aを読むたびスタックにプッシュ、bを読むたびポップ、空になれば受理。③有限オートマトンの表現力を真に超えるが、チューリング機械には及ばない。
出典: AI生成問題（学習用）