Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 07:19, 7 June 2006

Revision as of 13:52, 25 September 2006

Line 3:

==Formal definition==

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

* a finite set of states (''S'')

* a finite set call the alphabet (ΣΣ)

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

* a start state (''s'' ∈∈ ''S'')

* an accept state (''a'' ∈∈ ''S'')

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

A [[deterministic finite automaton|DFA]] or [[nondeterministic finite automaton|NFA]] can easily be converted into a GNFA and then the GNFA can be easily converted into a [[regular expression]] by repeatedly collapsing parts of it to single edges until ''S'' = {''s'', ''a''}. Similarly, GNFAs can be reduced to NFAs by changing regular expression operators into new edges until each edge is labelled with a regular expression matching a single string of length at most 1. NFAs, in turn, can be reduced to DFAs using the [[powerset construction]]. This shows that GNFAs recognize the same set of [[formal language]]s as DFAs and NFAs.