Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 15:42, 29 October 2012

Revision as of 15:31, 23 November 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 gNFAGNFA must have only one start state and one accept state, and these cannot be the same state, whereas a NFA or DFA both may have several accept states, and the start state can be an accept state. A gNFAGNFA must have only one transition between any two states, whereas a NFA or DFA both allow for numerous transitions between states. In a gNFAGNFA, 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==