問題
オートマトン理論における「決定性有限オートマトン（DFA）」と「非決定性有限オートマトン（NFA）」の関係として正しいものはどれか。
選択肢
- 1ア DFAとNFAでは受理できる言語が異なる
- 2イ 任意のNFAは等価なDFAに変換可能であり、受理する言語は同じ
- 3ウ NFAの方が受理できる言語が多い
- 4エ DFAはNFAに変換できない
解答と解説を見る
正解
2. イ 任意のNFAは等価なDFAに変換可能であり、受理する言語は同じ
解説
任意のNFAは部分集合構成法により等価なDFAに変換可能であり、両者が受理する言語のクラスは正規言語で同一です。