非決定性有限オートマトン
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2023年9月) |
非決定性有限オートマトン(ひけっていせいゆうげんオートマトン、英: nondeterministic finite automaton、NFA)または非決定性有限状態機械(ひけっていせいゆうげんじょうたいきかい、英: nondeterministic finite state machine)は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。
直感的説明
NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。
M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S2, S1} を持ち、もうひとつは状態 {S3, S4} を持つ。
- 最終状態 S1 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 S2 にあるときは奇数個であることを意味する。1 が入力されたとき、上のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 0 が含まれていた事がわかる。
- 最終状態 S3 にあるとき、それまでの入力文字列に偶数個の 1 が含まれていたことを意味し、状態 S4 にあるときは奇数個であることを意味する。0 が入力されたとき、下のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 1 が含まれていた事がわかる。
非決定性有限オートマトンと同じ種類の言葉
- 非決定性有限オートマトンのページへのリンク