非決定性有限オートマトンとは？
非決定性有限オートマトンとは一言で言えば、「次の状態が一意に決定しない状態数が有限個のオートマトン」です。英語では「Nondeterministic Finite Automaton」と書くので、頭文字を取って「NFA」とも呼ばれます。
先に決定性有限オートマトンについて理解しておいた方がいいので、まだ理解できてない方はこちらの「決定性有限オートマトン(DFA)を分かりやすく解説！」をご覧ください！
また、オートマトンについて理解したい方はこちら「オートマトンとは何か？分かりやすく解説します！」
まずは非決定性有限オートマトンの重要な性質から説明します。
非決定性有限オートマトンの重要な性質
非決定性有限オートマトンには以下のような２つの重要な性質があります。
・次の状態が一意に決定しない
・入力文字がなくても自由に他の状態へ遷移できる$\varepsilon$遷移がある（ただし、$\varepsilon$遷移はなくても良い）
特に「次の状態が一意に決定しない」という性質は非常に重要です。もし、「次の状態が一意に決定する」のであれば、それはただの決定性有限オートマトンで、非決定性有限オートマトンではありません。
例えば、以下のようなオートマトンを考えましょう。
このオートマトンは状態２で入力$b$に対する遷移先が２つあります。これが「次の状態が一意に決定しない」の意味です。
また、状態１から状態４への$\varepsilon$と書かれている遷移が「$\varepsilon$遷移」です。$\varepsilon$遷移は入力文字に関係なく自由に状態を遷移することができるもので、「どこにでも・何個でも」作ることができます。
例えば、次のように$\varepsilon$遷移を2回繋げることもできます。つまり、このオートマトンなら、「初期状態１→状態４→状態２」という遷移が入力文字なしで可能なのです。
てことは、$\varepsilon$遷移があれば「次の状態が一意に決定しない」状態があるから、非決定性有限オートマトンだと言えるってことっすか？
一概にはそうとは言えません！
例えば、次のようなオートマトンの場合、確かに$\varepsilon$遷移は存在するのですが、状態２から状態２への遷移なので、「次の状態が一意に決定する」と言えると思います。
なので、非決定性有限オートマトンではないと思うのですが、状態２を$\varepsilon$遷移前と後で違う状態だと考えるなら、非決定性有限オートマトンと言えるかもしれません。
もしこれの真相が分かる方がいましたら、教えてください。
非決定性オートマトンの例
いくつかの例を見て非決定性有限オートマトンのイメージを捉えましょう。
例１
例えば、次のようなオートマトンは非決定性オートマトンです。
なぜこのオートマトンは非決定性有限オートマトンなのか分かりますか？
状態１で、$a$が入力のときの遷移先が2つあるからっすね！
その通り！
例２
次のようなオートマトンも非決定性オートマトンです。
これは状態１で$b$が入力のときの遷移先が2つあって、状態２から状態４への$\varepsilon$遷移があるからですよね。
その通りです！
例題
以下の非決定性有限オートマトンについて次の問に答えよ。
（１）文字列「$bbaaaba$」は受理されるか？
（２）受理する文字列を正規表現で答えよ。
（１）受理されない
（２）$b^{*}aa^{*}|b^{*}aa^{*}b$
まとめ
・非決定性有限オートマトンの性質
・次の状態が一意に決定しない
・入力文字がなくても自由に他の状態へ遷移できる$\varepsilon$遷移がある
・$\varepsilon$遷移は入力文字に関係なく自由に状態を遷移することができるもので、「どこにでも・何個でも」作ることが出来る
・非決定性有限オートマトンの性質
・次の状態が一意に決定しない
・入力文字がなくても自由に他の状態へ遷移できる$\varepsilon$遷移がある
・$\varepsilon$遷移は入力文字に関係なく自由に状態を遷移することができるもの。「どこにでも・何個でも」作ることが出来る