決定性有限オートマトン（DFA）が受理する言語のクラスと、非決定性有限オートマトン（NFA）が受理する言語のクラスの関係として、正しいものはどれか。

解説

正解は「両者は等しい」です。DFA は NFA の特別な場合（各状態・各入力記号の遷移先がちょうど1つ）なので、DFA が受理する言語は NFA でも受理できます。逆に、任意の NFA は、NFA の状態の集合を DFA の1つの状態とみなす部分集合構成法によって、同じ言語を受理する DFA に変換できます。空動作（ε遷移）を含む NFA も同様で、どれも正規言語のクラスを受理します。非決定性は表現を簡潔にしますが、能力は増やしません。「DFAの方が真に大きい」「NFAの方が真に大きい」はどちらも誤りです。「互いに一方に含まれない言語がある」も、両者が等しいため誤りです。なお、プッシュダウンオートマトンでは決定性の方が真に弱くなります。