1.3 Graph Represen t a tions 21
a *b(c+da *b) *bFigure 1.6: Labeled digraph G(r) for Y = ab(c + dab)*.
In fact, if an E-edge is a unique out-edge from a nonfinal vertex or a unique
in-edge to a noninitial vertex when it is created, then it remains so after the
replacements are done in the construction.
Example 1.26 Construct G(r) for r = ab(c + dab)*.
SoZution. The construction is shown in Figure 1.6. Note that we made an
additional simplification at the final step.^0
Exercise 1.3
1. What is the shortest string in each of the following languages? What is
the shortest nonempty string in each language?
(a) 10 + (0 + ll)O*l.
(b) (00 + 11 + (01 + lO)(OO + ll)*(Ol+ lo))*.