[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.

• What if state Q has connections to more than two other states, say, Qi, Qj, and Qk? Then you have to consider these states pairwise: Qi with Qj, Qj with Qk, and Qi with Qk.
• What if some of the arcs in the original state are missing? There are too many cases to work this out in detail, but you should be able to figure it out for any specific case, using the above as a model.
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.