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.

Copyright © 1996 by David Matuszek

Last modified Feb 5, 1996