[Overview] [Previous] [Next]

From NFAs to Regular Expressions (Part I)

Creating a regular expression to recognize the same strings as an nfa is trickier than you might expect, because the nfa may have arbitrary loops and cycles. Here's the basic approach (details supplied later):

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.

The regular expression derived in the final step accepts the same language as the original nfa.

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.