• NFA は非決定性有限オートマトンの略です。特定の通常言語については、DFA よりも NFA を構築するのが簡単です。
• 現在の状態から次の状態への特定の入力に対するパスが多数存在する場合、有限オートマトンは NFA と呼ばれます。
• すべての NFA は DFA ではありませんが、各 NFA は DFA に変換できます。
• NFA は DFA と同じ方法で定義されますが、次の 2 つの例外を除き、複数の次の状態と ε 遷移が含まれます。

次の画像では、入力 a の状態 q0 から、次の 2 つの状態 q1 と q2 があり、同様に、入力 b の q0 から、次の状態は q0 と q1 であることがわかります。したがって、特定の入力で次にどこに進むかは固定または決定されません。したがって、この FA は非決定性有限オートマトンと呼ばれます。

NFA の正式な定義:

NFA にも DFA と同じ 5 つの状態がありますが、次に示すように遷移関数が異なります。

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

どこ、

抽象クラスとインターフェイス

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

NFA のグラフィック表現

NFA は状態図と呼ばれる有向グラフで表現できます。その中で：

1. 状態は頂点で表されます。
2. 入力文字のラベルが付いた円弧は遷移を示します。
3. 初期状態は矢印でマークされています。
4. 最終状態は二重丸で示されます。

例 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

解決：

遷移図:

遷移表:

上の図では、現在の状態が q0 の場合、入力 0 では次の状態は q0 または q1 になり、入力 1 では次の状態は q1 になることがわかります。現在の状態が q1 の場合、入力 0 では次の状態は q2 になり、入力 1 では次の状態は q0 になります。現在の状態が q2 の場合、0 入力の次の状態は q2 で、1 入力の次の状態は q1 または q2 になります。

例 2:

∑ = {0, 1} の NFA は、01 を持つすべての文字列を受け入れます。

解決：

遷移表:

例 3:

∑ = {0, 1} の NFA で、長さが 2 以上のすべての文字列を受け入れます。

解決：

遷移表: