1.3 Graph Representations 19
Figure 1.4: Labeled digraph G(r) for T = (11 + O)*(OO + l)*.- Theorem 1.25 Let r be a regular expression. Then, an E-edge (u,v) in
G(r) which is a unique out-edge from a nonfinal vertex u or a unique in-edge
to a noninitial vertex v can be shrunk into a single vertex, still preserving the
property of Theorem 1.23. (If one of the endpoints of the E-edge is the initial
vertex or the final vertex, then so is the resulting vertex.)Proof. To see why such an E-edge can be deleted, suppose that an E-edge (u, v)
is the unique out-edge from u, and suppose that u is not the final vertex. Let
G’(r) be the graph obtained from G(r) by shrinking the edge (u, v) to a single
vertex w. Let vr be the initial vertex of G(r) and vf be the final vertex of
G(r). We need to show that for each path 7r in G(r) from vr to vf, there is a
path r’ in G’(r) from vr to vf with the same lables as 7r, and vice versa.
Let 7r be a path in G(r) from vr to VI. If it does not pass through vertex
u, then the same path exists in G’(r) and all their labels remain the same. If
7r passes through u, then we can divide it into two subpaths, one from v1 to
the first occurrence of u and the other from the first u to vf. Since (u, v) is
the only out-edge from u, the second subpath must start with this edge (u, v),