Revision as of 09:47, 10 March 2016 edit BG19bot (talk \| contribs) 1,005,055 edits m →References: Remove blank line(s) between list items per WP:LISTGAP to fix an accessibility issue for users of screen readers. Do WP:GENFIXES and cleanup if needed. Discuss this at Wikipedia talk:WikiProject Accessibility#LISTGAP ← Previous edit		Revision as of 03:24, 10 November 2016 edit undo Zziccardi (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 7,990 edits General fixes Tags: Mobile edit Mobile web edit Next edit →
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~~]] (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.▼ ~~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, 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. ==Formal definition==

Generalized nondeterministic finite automaton: Difference between revisions