非決定性有限オートマトン

非決定性有限オートマトン（ひけっていせいゆうげん-（）、英: Nondeterministic Finite Automaton）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい（）、英: Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。

直感的説明

NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。

[math]S_1 \overset{c_1}{\longrightarrow} S_2 \overset{c_2}{\longrightarrow} \cdots \overset{c_{n-1}}{\longrightarrow} S_n[/math]

非決定性と呼ばれるのは、ある状態からの遷移先が入力文字だけでは一意に定まらない場合があることと、入力文字を受け取らなくても状態遷移する場合があることからである。例えば、状態 S₁ にあって文字 a が入力された場合、この文字を受け取らずに状態 S₂ に遷移してから a を受け取って状態 S₃ に遷移することが可能である。

[math]S_1 \overset{\varepsilon}{\longrightarrow} S_2 \overset{a}{\longrightarrow} S_3[/math]

入力文字を受け取らずに遷移することを「イプシロン遷移」と呼ぶ。一般にギリシャ文字を使って「ε-遷移」と記述する。状態遷移図では、入力文字の代わりに ε を付記する。

最後の入力文字を受け取ったとき、NFA がある特定の状態（受容状態）になった場合のみ、その入力文字列をNFAが受容したと判断される。一方、受容状態以外で終了した場合、その入力文字列は拒否されたと判断される。

形式的定義

非決定性有限オートマトン（NFA）は、[math]\{S, \Sigma, T, s_0, A\}[/math] の5つの要素から構成され、各要素は以下のような性質を持つ。

• 状態の有限集合（[math]S[/math]）
• 入力文字の有限集合（[math]\Sigma[/math]）
• 遷移関数（[math]T:S \times (\Sigma \cup {\varepsilon}) \rarr P(S)[/math]）
• 状態 [math]s_0[/math] を特に「初期（または開始）状態」として区別する（[math]s_0 \in S[/math]）
• 状態の集合 [math]A[/math] を特に「受容（または終了）状態」として区別する（[math]A \subseteq S[/math]）

ここで [math]P(S)[/math] は [math]S[/math] の冪集合であり、[math]\varepsilon[/math] は空の文字列であり、[math]\Sigma[/math] は入力文字群である。

[math]\mathbf{M}[/math] が [math]\mathbf{M} = (S, \Sigma, T, s_0, A)[/math] で構成される NFA で、[math]X[/math] が [math]\Sigma[/math] に含まれる文字で構成された文字列とする。[math]\mathbf{M}[/math] が文字列 [math]X[/math] を受容するのは、以下の条件が成立した場合である。まず、[math]X[/math] を [math]x_1, x_2 \cdots x_n, x_i \in (\Sigma \cup {\varepsilon})[/math] と表したときに、これを入力された [math]\mathbf{M}[/math] がとる状態遷移が [math]r_0, r_1, \cdots r_n, r_i \in S[/math] のようになるとき、以下の条件が成り立つ。

1. [math]r_0 = s_0[/math]
2. [math]r_i \in T(r_{i-1}, x_i), for\,i = 1, \cdots, n[/math]
3. [math]r_n \in A[/math]

マシンは初期状態 [math]s_0[/math] から開始され、入力文字列を読み込む。オートマトンは遷移関数 [math]T[/math] に現在状態と入力文字（あるいは空の文字）を与えて次に遷移すべき状態を得る。しかし、「NFA の次の状態は現在の入力イベントのみで決定されるのではなく、その後の任意個数の入力イベント（文字列）にも影響される。NFAが影響される入力イベントが続く限り、次の遷移先を決定することはできない」[1]。オートマトンが読み込みを終了したときに受容状態にあれば、NFA はその入力文字列を受容したと言える。さもなくば、その入力文字列は拒否されたと見なされる。

ある NFA が受容する文字列全体の集合が NFA の受容する言語である。この言語は正規言語の範囲に一致する。

NFAとDFAの関係

任意のNFAには、それと同じ言語を受容する決定性有限オートマトン（DFA）が存在する。実用的なオートマトンを得るために、しばしばNFAはDFAに変換される。

NFAをDFAに変換するには、NFAにおける上述した [math]P(S)[/math] の各要素を、DFAにおける1状態とすればよい。この変換は冪集合構築、または部分集合構成法という。しかし最悪の場合、この変換により必要な状態数が指数関数的に増大する。

実装

NFA を実装する方法はいくつか存在する。

• 決定性有限オートマトンに変換する。全ての NFA は DFA に変換可能である。
• 複数の状態への遷移について、配列のようなデータ構造を使って、遷移可能な状態に印を付ける（状態番号をインデックスとする配列）。印が付いている複数の状態が取りうる状態と見なされ、入力にしたがって取りうる全ての状態について遷移先を判断する（ある状態は入力文字を受け付けない場合もあり、その場合その状態は捨てられる）。このようにして最終的に受容状態に印がついていたら、その入力文字列が受容されたと判断できる。
• オブジェクト指向的な実装方法として、NFA をオブジェクトとして、遷移先が複数存在する場合に遷移先の個数ぶんのオブジェクトのコピーを作成してそれぞれに同じ入力文字列（の未入力分）を与えるという方法がある。最終的に受容状態となった NFA オブジェクトが存在したら、その文字列が受容されたと判断できる。現在状態と未入力の入力文字列を引数とした再帰関数の形でも同じことが可能である。

例

以下では、1 および 0 を入力文字とする NFA [math]\mathbf{M}[/math] を例として示す。[math]\mathbf{M}[/math] は入力文字列に偶数個の 0 がある場合（最終状態[math]S_1[/math]）と、偶数個の 1 がある場合（最終状態[math]S_3[/math]）を受容する。

[math]\mathbf{M} = (S, \Sigma, T, s_0, A)[/math] において、

[math] \begin{cases} \Sigma = \{0, 1\} \\ S = \{S_0, S_1, S_2, S_3, S_4\} \\ s_0 = S_0 \\ A = \{S_1, S_3\} \\ T \end{cases} [/math]

遷移関数 T は以下の状態遷移表で定義される。

	[math]0[/math]	[math]1[/math]	[math]\varepsilon[/math]
[math]S_0[/math]	[math]\{\}[/math]	[math]\{\}[/math]	[math]\{S_1, S_3\}[/math]
[math]S_1[/math]	[math]\{S_2\}[/math]	[math]\{S_1\}[/math]	[math]\{\}[/math]
[math]S_2[/math]	[math]\{S_1\}[/math]	[math]\{S_2\}[/math]	[math]\{\}[/math]
[math]S_3[/math]	[math]\{S_3\}[/math]	[math]\{S_4\}[/math]	[math]\{\}[/math]
[math]S_4[/math]	[math]\{S_4\}[/math]	[math]\{S_3\}[/math]	[math]\{\}[/math]

M の状態遷移図は以下のようになる。

300px

M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S₂, S₁} を持ち、もうひとつは状態 {S₃, S₄} を持つ。

最終状態 S1 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 S2 にあるときは奇数個であることを意味する。1 が入力されたとき、上のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 0 が含まれていた事がわかる。

最終状態 S3 にあるとき、それまでの入力文字列に偶数個の 1 が含まれていたことを意味し、状態 S4 にあるときは奇数個であることを意味する。0 が入力されたとき、下のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 1 が含まれていた事がわかる。

Mの言語は以下の正規表現で記述される正規言語である。

[math](1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*) [/math]

拡張NFA（GNFA）

拡張非決定性有限オートマトン（GNFA）または拡張非決定性有限状態機械とは、各状態遷移が任意の正規表現に対応する NFA である。GNFA は入力からまとめて複数の文字を読み込むが、その文字列は遷移（エッジ）に付記された正規表現に対応するものである。

形式的定義

GNFA は、[math](S, \Sigma, T, s, a)[/math] の5要素から構成され、各要素は以下の性質を持つ。

• 状態の有限集合（[math]S[/math]）
• 入力文字の有限集合（Σ）
• 遷移関数（[math]T: (S - \{a\}) \times (S - \{s\}) \rarr R[/math]）
• 開始状態（[math]s \in S[/math]）
• 受容状態（[math]a \in S[/math]）

ここで [math]R[/math] は文字集合 [math]\Sigma[/math] から構成される全ての正規表現の集合である。

DFA や NFAは簡単に GNFA に変換でき、GNFA は正規表現に簡単に変換できる。その変換は、中間的な遷移を正規表現に変換していき、最終的に [math]S = \{s, a\}[/math] というひとつの遷移（エッジ）になるようにするものである。同様に GNFA の各遷移（エッジ）に付記された正規表現を一文字ずつに分解するまで中間状態を追加していけば NFA に変換できる。さらに NFA は前述したように DFA に変換可能である。したがって GNFA は DFA および NFA と等価な形式言語を理解する。