Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 01:29, 29 December 2006

Revision as of 01:29, 29 December 2006

Line 1:

In the [[theory of computation]], a '''generalized nondeterministic finite state machine''' or '''generalized nondeterministic finite automaton (GNFA)''' is a [[nondeterministic finite state machine|NFA]] where each transition may be labeled with any regular expression. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition.

ryan ryan ryan

==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 called 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.

[[Category:Computational models]]

[[ja:非決定性有限オートマトン]]