Revision as of 11:40, 30 December 2006 edit 193.198.150.48 (talk) +hr interlink ← Previous edit		Revision as of 21:45, 29 May 2007 edit undo Linas (talk \| contribs) 25,539 edits recat to Category:Automata so it lives with similar articles Next edit →
Line 13: 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. [[Category:~~Computational models~~Automata]] [[hr:Poopćeni nedeterministički konačni automat]]

Generalized nondeterministic finite automaton: Difference between revisions