Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 06:45, 14 May 2004

Revision as of 07:11, 14 May 2004

Line 4:

A GNFA can be defined as a [[n-tuple|5-tuple]]: (''S'', Σ, ''T'', ''s'', ''a'')

* Σ is a finite set of symbolsstates (''S'')

* ''S'' is a finite set of statessymbols (Σ)

* a transition [[function (mathematics)|function]] (''T'' : (''S'' -{''a''}) × (''S'' - {''s''}) → ''R'')

* Σ is a finite set of symbols

* ''T''a :start state (''Ss'' -{''a''}) &timesisin; (''S'' - {''s''}) → ''R''

* an accept state (''sa'' ∈ ''S'' is the start state)

Wherewhere ''R'' is the collection of all [[regular expressions]] over the alphabet Σ.

* ''a'' ∈ ''S'' is the accept state

Where ''R'' is the collection of all [[regular expressions]] over the alphabet Σ.

A DFA or NFA can easily be converted into a GNFA and then the GNFA can be easily converted into a [[regular expression]] by reducing the number of states until ''S'' = {''s'', ''a''}.