Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 12:17, 4 December 2011

Revision as of 10:34, 30 January 2012

Line 1:

In the [[theory of computation]], a '''generalized nondeterministic finite automaton (GNFA)''', also known as '''expression automaton'''

or '''generalized nondeterministic finite state machine''' is a variation of

[[nondeterministic finite automaton|NFA]] where each transition is 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. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A gNFA must have only one start state and one accept state, and these cannot be the same state, where aswhereas a NFA or DFA both may have several accept states, and the start state can be an accept state. A gNFA must have only one transition between any two states, where aswhereas a NFA or DFA both allow for numerous transitions between states. In a gNFA, a state has a single transition to every state in the machine, although often it is a convention to ignore the transitions that are labelled with the empty set when drawing generalized nondeterministic finite state machines.

==Formal definition==

Line 9:

* 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 Σ.

Line 16:

==References==

* Yo-Sub Han and Derick Wood. "The Generalization of Generalized Automata: Expression Automata." In: 9th International [[Conference on Implementation and Application of Automata]], CIAA 2004, Kingston, Canada, July 22-2422–24, 2004, Revised Selected Papers, [[LNCS]] 3317, pp. 156-166 156–166. doi:10.1007/b105090

* Michael Sipser. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing.

Line 22:

==External links==

* A graphical description of GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found at [http://www.cs.sunysb.edu/~cse350/slides/rgExp2.pdf]

[[Category:Automata theory]]