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):
The regular expression derived in the final step accepts the
same language as the original nfa.
- 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