非決定性有限オートマトン
拡張非決定性有限オートマトン(GNFA)または拡張非決定性有限状態機械とは、各状態遷移が任意の正規表現に対応する NFA である。GNFA は入力からまとめて複数の文字を読み込むが、その文字列は遷移(エッジ)に付記された正規表現に対応するものである。
非決定性有限オートマトン (NFA) は、 ( S , Σ , T , s 0 , A ) {\displaystyle (S,\Sigma ,T,s_{0},A)} の5つの要素から構成され、各要素は以下のような性質を持つ。
状態の有限集合( S {\displaystyle S} )
入力文字の有限集合( Σ {\displaystyle \Sigma } )
遷移関数( T : S × ( Σ ∪ ε ) → P ( S ) {\displaystyle T:S\times (\Sigma \cup {\varepsilon })\rightarrow P(S)} )
状態 s 0 {\displaystyle s_{0}} を特に「初期(または開始)状態」として区別する( s 0 ∈ S {\displaystyle s_{0}\in S} )
状態の集合 A {\displaystyle A} を特に「受容(または終了)状態」として区別する( A ⊆ S {\displaystyle A\subseteq S} )
ここで P ( S ) {\displaystyle P(S)} は S {\displaystyle S} の冪集合であり、 ε {\displaystyle \varepsilon } は空の文字列であり、 Σ {\displaystyle \Sigma } は入力文字群である。