Content deleted Content added
m link finite set |
|||
Line 12:
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.
A great PDF, graphically describing GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found at www.cs.uiowa.edu/~rus/Courses/Theory/Notes/rgExp2.pdf
[[Category:Automata]]
| |||