Content deleted Content added
No edit summary |
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1:
In the [[theory of computation]], a '''generalized nondeterministic finite automaton''' ('''GNFA'''), also known as an '''expression automaton''' or a '''generalized nondeterministic finite state machine''', is a variation of a
[[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, whereas
==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 start state (''s'' ∈ ''S'');
* an accept state (''a'' ∈ ''S'');
Line 21 ⟶ 20:
* 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:Finite-state
|