- If the nfa has more than one final state, convert it to an nfa with only one final state. Make the original final states nonfinal, and add a transition from each to the new (single) final state.
- Consider the nfa to be a
*generalized transition graph,*which is just like an nfa except that the edges may be labeled with arbitrary regular expressions. Since the labels on the edges of an nfa may be either or members of , each of these can be considered to be a regular expression. - Remove states one by one from the nfa, relabeling edges as you go, until only the initial and the final state remain.
- Read the final regular expression from the two-state automaton that results.

Since we can convert an nfa to a regular expression, and we can convert a regular expression to an nfa, the two are equivalent formalisms--that is, they both describe the same class of languages, the regular languages.

Copyright © 1996 by David Matuszek

Last modified Feb 5, 1996