Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 14:13, 8 May 2019

Revision as of 14:13, 8 May 2019

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 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, whereas 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. Bigger and better than a woman who likes the wolf in sheep’s clothes for the vegetarian meal that they are not sure of and they have to drink water.

==Formal definition==