次の問題のうち、決定可能である（必ず停止して正しく判定するアルゴリズムが存在する）ものはどれか。

解説

正解は「与えられた DFA が受理する言語が空かどうか」です。DFA の状態遷移図を開始状態から幅優先探索などでたどり、受理状態に到達できるかを調べれば、有限の手順で必ず判定できます。正規言語については、2つの DFA が同じ言語を受理するかなど、多くの性質が決定可能です。「与えられた文脈自由文法が曖昧かどうか」は決定不能であることが知られています。「与えられたチューリング機械が、空テープから始めて停止するかどうか」は、停止性問題を帰着でき、決定不能です。「与えられた2つの文脈自由文法が同じ言語を生成するかどうか」も決定不能です。なお、1つの文脈自由文法の言語が空かどうかは決定可能です。