Content deleted Content added
NPOV, structure |
reference added |
||
Line 1:
In the [[theory of computation]], a '''generalized nondeterministic finite state machine''', also known as '''expression automaton'''
or '''generalized nondeterministic finite automaton (GNFA)''' is a [[nondeterministic finite state machine|NFA]] where each transition may be 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. ==Formal definition==
Line 13 ⟶ 14:
A [[deterministic finite automaton|DFA]] or [[nondeterministic finite automaton|NFA]] can easily be converted into a GNFA and then the GNFA can be easily converted into a [[regular expression]] 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 [[powerset construction]]. This shows that GNFAs recognize the same set of [[formal language]]s as DFAs and NFAs.
==References==
* Yo-Sub Han and Derick Wood. "The Generalization of Generalized Automata: Expression Automata." In: 9th International
[[Conference on Implementation and Application of Automata]], IAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers,
[[LNCS]] 3317, pp. 156-166. doi:10.1007/b105090
==External links==
| |||