問題
有限オートマトンに関する記述として、適切なものはどれか。
ア）有限オートマトンは、無限個の状態を持つことができる計算モデルである。
イ）決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）は、受理できる言語のクラスが異なる。
ウ）有限オートマトンの状態遷移は、現在の状態と入力記号によって一意に決まるものだけを指す。
エ）任意のNFAに対して、それと等価なDFAを構成することができる。
解答・解説を見る
正解： エ）
解説：
- ア）有限オートマトンは「有限」個の状態を持つ計算モデルであり、無限個の状態は扱えません。誤りです。
- イ）DFAとNFAは受理できる言語のクラス（正規言語）は同じです。表現力は同等であり、誤りです。
- ウ）「現在の状態と入力記号によって一意に決まる」のはDFAの定義です。NFAは複数の遷移先を持てるため、この記述は有限オートマトン全般には当てはまりません。誤りです。
- エ）部分集合構成法（subset construction）により、任意のNFAと等価なDFAを構成できることが知られています。正解です。
重要キーワード
| 用語 | 説明 |
|---|---|
| DFA | 決定性有限オートマトン。状態遷移が一意に決まる |
| NFA | 非決定性有限オートマトン。複数の遷移先を持ちうる |
| 正規言語 | 有限オートマトンで受理可能な言語のクラス |
| 部分集合構成法 | NFAから等価なDFAを構成するアルゴリズム |