非決定性有限オートマトン
GNFA は、 ( S , Σ , T , s , a ) {\displaystyle (S,\Sigma ,T,s,a)} の5要素から構成され、各要素は以下の性質を持つ。
状態の有限集合( S {\displaystyle S} )
入力文字の有限集合(Σ)
遷移関数( T : ( S − { a } ) × ( S − { s } ) → R {\displaystyle T:(S-\{a\})\times (S-\{s\})\rightarrow R} )
開始状態( s ∈ S {\displaystyle s\in S} )
受容状態( a ∈ S {\displaystyle a\in S} )
ここで R {\displaystyle R} は文字集合 Σ {\displaystyle \Sigma } から構成される全ての正規表現の集合である。
DFA や NFAは簡単に GNFA に変換でき、GNFA は正規表現に簡単に変換できる。その変換は、中間的な遷移を正規表現に変換していき、最終的に S = { s , a } {\displaystyle S=\{s,a\}} というひとつの遷移(エッジ)になるようにするものである。同様に GNFA の各遷移(エッジ)に付記された正規表現を一文字ずつに分解するまで中間状態を追加していけば NFA に変換できる。さらに NFA は前述したように DFA に変換可能である。したがって GNFA は DFA および NFA と等価な形式言語を理解する。