Scanning—Theory and Practice - Crafting a Compiler - page 102

T 2. It, too, allows us to bypass a state. Suppose state s has a transition to state
r labeled X and state r has a transition to itself labeled Z ,aswellasatransition
to state u labeled Y . We can go directly from state s to state u with a transition
labeled XZ Y .The Z term reflects that once we reach state r , we can cycle
back into r zero or more times before finally proceeding to u .
We use transformations T 2and T 3 as follows. We consider, in turn, each
pair of predecessors and successors a state s has and use T 2or T 3 to link
a predecessor state directly to a successor state. In this case, s is no longer
needed—all paths through the FA can bypass it. Since s is not needed, we
remove it. The FA is now simpler because it has one fewer states. By removing
all states other than the start state and the accepting state (using transformation
T 1 when necessary), we will reach our goal. We will have an FAwith only one
transition, and the label on this transition will be the regular expression we
want. F , shown in Figure 3.31, implements this algorithm. The algorithm

begins by invoking A

ind R e

, which introduces new start and accept states.
The loop at Marker 1 considers each state s of the FA in turn. Transformation
T 1 ensures that each pair of states is connected by at most one transition. This
transformation is performed prior to processing s at Marker 3 . State s is then
eliminated by considering the cross-product of states with edges to and from
s . For each such pair of states, transformation T 2or T 3 is applied. State s is
then removed at Marker 2 , along with all edges to or from state s .When
the algorithm terminates, the only states left are NewStart and NewAccept ,
introduced by A

ugment

. The regular expression for the FA labels the transition
between these two states.
As an example, we find the regular expression corresponding to the FA
in Section 3.8.2. The original FA, with a new start state and accepting state
added, is shown in Figure 3.32(a). State 1 has a single predecessor, state 0, and
a single successor, state 2. Using a T 3 transformation, we add an arc directly
from state 0 to state 2 and remove state 1. This is shown in Figure 3.32(b).
State 2 has a single predecessor, state 0, and three successors, states 2, 4, and 5.
Using three T 2 transformations, we add arcs directly from state 0 to states 3,
4, and 5. State 2 is removed. This is shown in Figure 3.32(c).
State 4 has two predecessors, states 0 and 3. It has one successor, state 5.
Using two T 2 transformations, we add arcs directly from states 0 and 3 to state
5. State 4 is removed. This is shown in Figure 3.32(d). Two pairs of transitions
are merged using T 1 transformations to produce the FA in Figure 3.32(e).
Finally, state 3 is bypassed with a T 2 transformation and a pair of transitions
is merged with a T 1 transformation, as shown in Figure 3.32(f). The regular
expression we obtain is

ugment

b ab ( a | b |λ | b aa | b a

)

By expanding the parenthesized subterm and then factoring a common term,