Generalized nondeterministic finite automaton

<h2 id="formal-definition">Formal definition</h2>
A GNFA can be defined as a <a href="/facts/N-tuple/BI1HIxL8">5-tuple</a>, (S, Σ, T, s, a), consisting of

<ul><li>a <a href="/facts/Finite_set/za1newlP">finite set</a> of states (S);</li>
<li>a finite set called the alphabet (Σ);</li>
<li>a transition <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> (T : (S 
 
 
 
 ∖
 
 
 {\displaystyle \setminus }
 
 {a}) × (S 
 
 
 
 ∖
 
 
 {\displaystyle \setminus }
 
 {s}) → R);</li>
<li>a start state (s ∈ S);</li>
<li>an accept state (a ∈ S);</li></ul>
where R is the collection of all regular expressions over the alphabet Σ.
The transition function takes as its argument a pair of two states and outputs a regular expression (the label of the transition). This differs from other finite state machines, which take as input a single state and an input from the alphabet (or the empty string in the case of nondeterministic finite state machines) and outputs the next state (or the set of possible states in the case of nondeterministic finite state machines). A <a href="/facts/Deterministic_finite_automaton/9conRLFS">DFA</a> or <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">NFA</a> can easily be converted into a GNFA and then the GNFA can be easily converted into a <a href="/facts/Regular_expression/KFL3veHX">regular expression</a> by repeatedly collapsing parts of it to single edges until S = {s, a}. Similarly, GNFAs can be reduced to NFAs by changing regular expression operators into new edges until each edge is labelled with a regular expression matching a single string of length at most 1. NFAs, in turn, can be reduced to DFAs using the <a href="/facts/Powerset_construction/FeTghmH7">powerset construction</a>. This shows that GNFAs recognize the same set of <a href="/facts/Formal_language/crDTyP8q">formal languages</a> as DFAs and NFAs.

<ul><li>Yo-Sub Han and <a href="/facts/Derick_Wood/dGFHnzJG">Derick Wood</a>. "The Generalization of Generalized Automata: Expression Automata." In: 9th International <a href="/facts/Conference_on_Implementation_and_Application_of_Automata/LBFX9ro4">Conference on Implementation and Application of Automata</a>, CIAA 2004, Kingston, Canada, July 22–24, 2004, Revised Selected Papers, <a href="/facts/LNCS/1UeA77BC">LNCS</a> 3317, pp. 156–166. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fb105090">10.1007/b105090</a></li>
<li><a href="/facts/Michael_Sipser/h5Wg22bh">Michael Sipser</a>. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>A graphical description of GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found at <a href="http://www.cs.sunysb.edu/~cse350/slides/rgExp2.pdf">[1]</a></li></ul>

Generalized nondeterministic finite automaton open-in-new

Generalized nondeterministic finite automaton