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
(you should verify that this is indeed the correct regular
All you have to do is plug in the correct values for
r1, r2, r3, and r4.
- 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.
Copyright © 1996 by David Matuszek
Last modified Feb 5, 1996