[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 Q_i in the original will leave you in Q_i in the replacement, and similarly for Q_j.

What if state Q has connections to more than two other states, say, Q_i, Q_j, and Q_k? Then you have to consider these states pairwise: Q_i with Q_j, Q_j with Q_k, and Q_i with Q_k.
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 r₁, r₂, r₃, and r₄ are (probably very complex) regular expressions. The resultant nfa represents the regular expression r₁*r₂(r₄ + r₃r_1*r₂)* (you should verify that this is indeed the correct regular expression). All you have to do is plug in the correct values for r₁, r₂, r₃, and r₄.