一般化非決定性有限オートマトン

一般化非決定性有限オートマトン（GNFA と略します）は、遷移にアルファベットの記号だけでなく、正規表現も書ける非決定性オートマトンです。

定義

GNFA は、有限オートマトンを正規表現に変換するアルゴリズムの途中で必要になります。GNFA は、遷移が正規表現で定められた NFA です。GNFA の例を見てみましょう。

図を見ると、例えば状態 q₂ から状態 q_f への遷移があり、正規表現 a^∗ b がつけられています。GNFA には、さらに次の条件があります。

• 初期状態 q₀ からは、ほかのすべての状態への遷移がなければなりません。図でも、状態 q₀ からほかのすべての状態へ遷移が出ています。
• GNFA の受理状態は1つだけで、ほかのすべての状態からこの状態への遷移があります。図のとおり、どの状態からも q_f に向かう矢印が出ています。
• 初期状態と受理状態は同じであってはいけません。そのため、GNFA の状態は少なくとも2つあります。
• 初期状態と受理状態以外のすべての状態からは、初期状態と受理状態以外のすべての状態への遷移がなければなりません。自己ループ（状態 q_i から状態 q_i への遷移）も含みます。

ふつうの NFA から GNFA への変換

NFA が与えられていれば、GNFA への変換は簡単です。

1. 新しい初期状態 q_s をつくり、そこからもとの初期状態への ε 遷移をつくります。
2. 新しい受理状態 q_f をつくり、もとのすべての受理状態から状態 q_f への ε 遷移をつくります。もとの受理状態はふつうの状態にします。
3. 複数の遷移がある場合（例えば、状態 q₁ から状態 q₂ へ記号0でも記号1でも移れる場合）は、それらを1つの正規表現にまとめ、もとの記号をすべて和の演算子で結びます（つまり、矢印に正規表現 0|1 をつけます）。
4. 定義上あるべき遷移がオートマトンにない場合は、その遷移をつくり、正規表現 ∅ をつけます。このような遷移は決して実行されないので、オートマトンが受理する言語は変わりません。

こうしてできたオートマトンは、オートマトンを正規表現に変換するときに使えます。