Generalized nondeterministic finite automaton: Difference between revisions

Revision as of 12:15, 4 December 2011

Latest revision as of 06:30, 14 April 2025

(20 intermediate revisions by 18 users not shown)

Line 1:

In the [[theory of computation]], a '''generalized nondeterministic finite stateautomaton''' machine('''GNFA'''), also known as an '''expression automaton''' or a '''generalized nondeterministic finite state machine''', is a variation of a

or '''generalized [[nondeterministic finite automaton]] (GNFANFA)''' is an [[nondeterministic finite state machine|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, wherewhereas as aan 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, where aswhereas 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==

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'' &#x2216;<math>\setminus</math> {''a''}) &times;× (''S'' &#x2216;<math>\setminus</math> {''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 15 ⟶ 14:

==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&nbsp;156–166. {{doi:|10.1007/b105090}}

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

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

==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:AutomataFinite-state theorymachines]]

[[Category:Automata theory]]

[[hr:Poopćeni nedeterministički konačni automat]]

[[ja:非決定性有限オートマトン]]