[Overview] [Previous] [Next]

From NFAs to Regular Expressions (Part II)

There are two complicated parts to extracting a regular expression from an NFA: removing states, and reading the regular expression off the resultant two-state generalized transition graph.

Here's how to delete a state (this is taken with minor modifications from Figure 3.9 on page 85 of your textbook):

To delete state Q, where Q is neither the initial state nor the final state,
replace with .

You should convince yourself that this transformation is "correct", in the sense that paths which leave you in Qi in the original will leave you in Qi in the replacement, and similarly for Qj.

You will end up with an nfa that looks like this, where r1, r2, r3, and r4 are (probably very complex) regular expressions. The resultant nfa represents the regular expression
r1*r2(r4 + r3r1*r2)*
(you should verify that this is indeed the correct regular expression). All you have to do is plug in the correct values for r1, r2, r3, and r4.
Copyright 1996 by David Matuszek
Last modified Feb 5, 1996