非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。非決定性と呼ばれるのは、ある状態からの遷移先が入力文字だけでは一意に定まらない場合があることと、入力文字を受け取らなくても状態遷移する場合があることからである。例えば、状態 S にあって文字 a が入力された場合、この文字を受け取らずに状態 S に遷移してから a を受け取って状態 S に遷移することが可能である。入力文字を受け取らずに遷移することを「イプシロン遷移」と呼ぶ。一般にギリシャ文字を使って「ε-遷移」と記述する。状態遷移図では、入力文字の代わりに ε を付記する。最後の入力文字を受け取ったとき、NFA がある特定の状態（受容状態）になった場合のみ、その入力文字列をNFAが受容したと判断される。一方、受容状態以外で終了した場合、その入力文字列は拒否されたと判断される。非決定性有限オートマトン（NFA）は、formula_1 の5つの要素から構成され、各要素は以下のような性質を持つ。ここで formula_9 は formula_2 の冪集合であり、formula_11 は空の文字列であり、formula_3 は入力文字群である。formula_13 が formula_14 で構成される NFA で、formula_15 が formula_3 に含まれる文字で構成された文字列とする。formula_13 が文字列 formula_15 を受容するのは、以下の条件が成立した場合である。まず、formula_15 を formula_20 と表したときに、これを入力された formula_13 がとる状態遷移が formula_22 のようになるとき、以下の条件が成り立つ。マシンは初期状態 formula_5 から開始され、入力文字列を読み込む。オートマトンは遷移関数 formula_27 に現在状態と入力文字（あるいは空の文字）を与えて次に遷移すべき状態を得る。しかし、「NFA の次の状態は現在の入力イベントのみで決定されるのではなく、その後の任意個数の入力イベント（文字列）にも影響される。NFAが影響される入力イベントが続く限り、次の遷移先を決定することはできない」。オートマトンが読み込みを終了したときに受容状態にあれば、NFA はその入力文字列を受容したと言える。さもなくば、その入力文字列は拒否されたと見なされる。ある NFA が受容する文字列全体の集合が NFA の受容する言語である。この言語は正規言語の範囲に一致する。任意のNFAには、それと同じ言語を受容する決定性有限オートマトン（DFA）が存在する。実用的なオートマトンを得るために、しばしばNFAはDFAに変換される。NFAをDFAに変換するには、NFAにおける上述した formula_9 の各要素を、DFAにおける1状態とすればよい。この変換は冪集合構築、または部分集合構成法という。しかし最悪の場合、この変換により必要な状態数が指数関数的に増大する。NFA を実装する方法はいくつか存在する。以下では、1 および 0 を入力文字とする NFA formula_13 を例として示す。formula_13 は入力文字列に偶数個の 0 がある場合（最終状態formula_31）と、偶数個の 1 がある場合（最終状態formula_32）を受容する。formula_14 において、formula_34遷移関数 T は以下の状態遷移表で定義される。M の状態遷移図は以下のようになる。M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S, S} を持ち、もうひとつは状態 {S, S} を持つ。Mの言語は以下の正規表現で記述される正規言語である。拡張非決定性有限オートマトン（GNFA）または拡張非決定性有限状態機械とは、各状態遷移が任意の正規表現に対応する NFA である。GNFA は入力からまとめて複数の文字を読み込むが、その文字列は遷移（エッジ）に付記された正規表現に対応するものである。GNFA は、formula_36 の5要素から構成され、各要素は以下の性質を持つ。ここで formula_41 は文字集合 formula_3 から構成される全ての正規表現の集合である。DFA や NFAは簡単に GNFA に変換でき、GNFA は正規表現に簡単に変換できる。その変換は、中間的な遷移を正規表現に変換していき、最終的に formula_43 というひとつの遷移（エッジ）になるようにするものである。同様に GNFA の各遷移（エッジ）に付記された正規表現を一文字ずつに分解するまで中間状態を追加していけば NFA に変換できる。さらに NFA は前述したように DFA に変換可能である。したがって GNFA は DFA および NFA と等価な形式言語を理解する。

出典:wikipedia