6.1.7 Getting rid of “unget” transitions

Before we get rid of “unget” transitions, we need to first eliminate ε transitions. Assuming a machine M = (S,Σ,T,s,A) has no ε transitions, and T′ corresponds to the “unget” transitions, then we can do the following transformation.

• Combine (u,σ,v) ∈ T′ and (v,σ,w) ∈ T ∖ T′ into (u,σw) in T.
• Combine (u,σ,v) ∈ T′ and (v,σ,w) ∈ T′ into (u,σw) in T′.

Note that this transformation destroys the nice and clean connection between component DFAs.