非決定性有限オートマトン（NFA）
同じ入力で複数の状態に同時に遷移しうる有限オートマトン
🎲NFAとは
非決定性有限オートマトン（NFA＝Nondeterministic Finite Automaton）とは、DFAと同じく状態と遷移で文字列を判定するモデルですが、同じ状態・同じ入力に対して、行き先が複数あってもよいという点が決定的に違います。「非決定性」とは、次にどこへ進むかが1つに決まらず、すべての可能性を同時に試すという意味です。
身近な例で言うと、分かれ道を全部同時に進む探検隊に似ています。道が二股に分かれていたら、隊を分けて両方の道を一度に進みます。最終的に1人でもゴール（受理状態）にたどり着けば成功とみなすのがNFAです。「うまくいく道が1つでもあれば受理」という、いわば楽観的な探索です。
上のツールで▶ボタンを押すと、紫色の丸が増えたり減ったりするのが見えます。これが「いま同時にいる可能性のある状態の集合」です。1文字読むたびに、すべての分岐先がまとめてアクティブになります。
🌿同時に複数状態を辿る仕組み
NFAの動きを正しく理解するコツは、「今いる状態」ではなく「今いる状態の集合」を追うことです。読み進めるたびに、アクティブな状態の集合が次の集合へと丸ごと移り変わります。
1文字読むときの計算は次の通りです。
・① 現在の集合の各状態から、その文字で行ける先をすべて集める
・② 集めた行き先をまとめて、新しいアクティブ集合とする
・③ 行き先が1つも無い経路は消える（集合から外れる）
例えば集合が {n0, n1} のとき「0」を読むと、n0からの行き先と n1からの行き先を合わせたものが次の集合になります。最後まで読み終えたとき、集合の中に受理状態が1つでも含まれていれば「受理」です。NFAの遷移先が複数あることを許すぶん、空集合になる（どこにも進めず経路が全滅する）こともあります。
⚖️DFAとの違い
DFA（決定性）とNFA（非決定性）の違いは「行き先が1つに決まるか、複数あってよいか」の一点に集約されます。下の表で整理します。
| DFA（決定性） | NFA（非決定性） | |
|---|---|---|
| 遷移先 | 必ず1つ | 0個・1個・複数いずれも可 |
| 同時にいる状態 | 常に1つ | 状態の集合（複数） |
| 受理の条件 | 最後の状態が受理状態 | 集合に受理状態が1つでもあれば受理 |
| 図の書きやすさ | 状態数が増えがち | 少ない状態で簡潔に書ける |
| 表せる言語の範囲 | DFAとNFAは同じ（正規言語）— 表現力は完全に同じ | |
最も重要なのは「DFAとNFAの表現力は同じ」という事実です。NFAの方が自由に書けるので「強そう」に見えますが、どんなNFAも、状態の集合を1つの新しい状態とみなす「部分集合構成法」で等価なDFAに変換できるため、判定できる文字列の集合（正規言語）はぴったり同じになります。
使い分けの感覚としては、人間が設計するときはNFAの方が直感的で楽（「101を含む」のように欲しい条件を素直に書ける）、一方コンピュータが高速に判定するときはDFAの方が有利（迷いがなく1本道で進める）という関係です。実際の正規表現エンジンは、NFAで書いてDFAに変換して動かすことがよくあります。
