20 REGULAR LANGUAGES
;!i 0 E -@ 0 0 1 10 0
00
Figure 1.5: Simpler solution for Example 1.24.with label E. The shrinking of (u, v) into a single vertex w does not change
the first subpath and only shrinks the first edge (u, v) in the second subpathto w and does not change the corresponding labels. We continue this process
to replace every occurrence of edge (u, v) in the second subpath by w, while
preserving the labels. Eventually, we get a path X’ in G’(r) from ~1 to vf with
the same labels as path OTT in G(r).
Conversely, let r’ be a path from v1 to vf in G’(r). If it does not pass
through the vertex w, then it is also a path in G(r), with the same labels.
If it passes through w, then we let ~‘1 be its subpath from v1 to the first
occurrence of w and ni be its subpath from the first w to vf. Since (u, v)
is the unique out-edge from u, the first edge (w, z) in ni, if exists, must be
corresponding to an edge (v, X) in G( r> (or, if IX: = w then (w, w) corresponds
to (v,v)). Now, if the last edge of ni is (y, w), then either there is an edge(y, U) in G(r) or an edge (y, v) in G(r) which has the same label as (y,u)).
In the first case, we replace w of ni by the edge (u,v); in the second case,
we simply replace the vertex w by the vertex v. Thus, we have eliminated
an occurrence of w in r’ without changing its total labels. We continue this
process to eliminate all occurrences of w and we obatin a path 7r in G(r) with
the same total labels.
At this point, we observe that this path r must start at v1 and end at vf: Ifw is not the final vertex of G’(r), then we have not changed the last vertex of
X’ and so 7r and r’ end at the same vertex vf. If w is the final vertex of G’(r),
then v must be the final vertex of G(r), since u is known, by assumption, to
be a nonfinal vertex. Our replacement process above then lets the last vertex
of 7r be v = vf. This completes the proof for the first half of the theorem.
The second half can be proved by a similar argument.^0