問題
オートマトンに関する記述として、最も適切なものはどれか。
選択肢
- 1有限オートマトンは内部状態を持たない
- 2決定性有限オートマトンと非決定性有限オートマトンの認識能力は同等である
- 3プッシュダウンオートマトンはチューリングマシンと同等の計算能力を持つ
- 4正規表現で表される言語はチューリングマシンでしか認識できない
正解
2. 決定性有限オートマトンと非決定性有限オートマトンの認識能力は同等である
詳しい解説を見る解説を閉じる
解説
DFAとNFAは異なる遷移規則を持つが、認識できる言語のクラス（正規言語）は同等である。NFAは部分集合構成法でDFAに変換可能。プッシュダウンは文脈自由言語、チューリングマシンは帰納的可算言語を認識する。
一問一答
全400問を繰り返し学習