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

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

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

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

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

Summarize Timeline Top Qs Fact Check

非決定性有限オートマトン (NFA) は、${\displaystyle (S,\Sigma ,T,s_{0},A)}$ の5つの要素から構成され、各要素は以下のような性質を持つ。

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

ここで ${\displaystyle P(S)}$ は ${\displaystyle S}$ の冪集合であり、${\displaystyle \varepsilon }$ は空の文字列であり、${\displaystyle \Sigma }$ は入力文字群である。

${\displaystyle \mathbf {M} }$ が ${\displaystyle \mathbf {M} =(S,\Sigma ,T,s_{0},A)}$ で構成される NFA で、${\displaystyle X}$ が ${\displaystyle \Sigma }$ に含まれる文字で構成された文字列とする。${\displaystyle \mathbf {M} }$ が文字列 ${\displaystyle X}$ を受容するのは、以下の条件が成立した場合である。まず、${\displaystyle X}$ を ${\displaystyle x_{1},x_{2}\cdots x_{n},x_{i}\in (\Sigma \cup {\varepsilon })}$ と表したときに、これを入力された ${\displaystyle \mathbf {M} }$ がとる状態遷移が ${\displaystyle r_{0},r_{1},\cdots ,r_{n},r_{i}\in S}$ のようになるとき、以下の条件が成り立つ。

1. ${\displaystyle r_{0}=s_{0}}$
2. ${\displaystyle r_{i}\in T(r_{i-1},x_{i}){\text{ for }}i=1,\cdots ,n}$
3. ${\displaystyle r_{n}\in A}$

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

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

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

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

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

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