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

計算理論において、一般化非決定性有限オートマトン（GNFA）は、式オートマトンまたは一般化非決定性有限状態機械とも呼ばれ、各遷移に任意の正規表現がラベル付けされた非決定性有限オートマトン（NFA）の変種です 。GNFAは、遷移の正規表現によって定義される文字列を構成する記号のブロックを入力から読み取ります。標準的な有限状態機械と一般化非決定性有限状態機械にはいくつかの違いがあります。GNFAは開始状態と受理状態がそれぞれ1つずつしか存在できず、これらは同じ状態であってはなりませんが、NFAまたはDFAはどちらも複数の受理状態を持つことができ、開始状態は受理状態であっても構いません。GNFAは任意の2つの状態間の遷移が1つしか存在できませんが、NFAまたはDFAはどちらも状態間の遷移を多数許容します。 GNFAでは、ある状態は機械内のすべての状態に対して単一の遷移を持ちますが、一般化された非決定性有限状態機械を描く際には、空集合でラベル付けされた遷移を無視するのが慣例となっています。

GNFAは、( S , Σ, T , s , a )からなる5タプルとして定義できます。

• 有限個の状態（S）の集合。
• アルファベット（Σ）と呼ばれる有限集合。
• 遷移関数( T  : ( S )${\displaystyle \setminus }${ a }) × ( S${\displaystyle \setminus }${ s }) → R );
• 開始状態（s ∈ S）
• 受理状態（a ∈ S）

ここで、RはアルファベットΣ上のすべての正規表現の集合である。

遷移関数は、引数として 2 つの状態のペアを受け取り、正規表現 (遷移のラベル) を出力します。これは、入力として単一の状態とアルファベットからの入力 (または非決定性有限状態機械の場合は空文字列) を受け取り、次の状態 (または非決定性有限状態機械の場合は可能な状態の集合) を出力する他の有限状態機械とは異なります。DFAまたはNFA は、GNFA に簡単に変換でき、GNFA は、 S = { s , a }になるまでその一部を繰り返し単一のエッジに縮約することで、簡単に正規表現に変換できます。同様に、 GNFAは、正規表現演算子を新しいエッジに変更して、各エッジが最大 1 の長さの単一の文字列に一致する正規表現でラベル付けされるまで、NFA に還元できます。NFA は、べき集合構成を使用して DFA に還元できます。これは、GNFA がDFA および NFA と同じ形式言語の集合を認識することを示しています。

• Yo-Sub Han、Derick Wood。「一般化オートマタの一般化：式オートマタ」。第9回オートマタの実装と応用に関する国際会議（CIAA 2004）、カナダ、キングストン、2004年7月22～24日、改訂版選集、LNCS 3317、pp.  156–166。doi ：10.1007/b105090
• マイケル・シプサー。2006年。『計算理論入門』（第2版）。インターナショナル・トムソン・パブリッシング。

• GNFAの図解と、GNFAを使用してNFAを正規表現に変換するプロセスについては、以下を参照してください。