Problem Solving in Automata, Languages, and Complexity

REGULAR LANGUAGES

Figure 1.3: Graph G(r) for regular expression r.

S: z E L(r) if and only if there is a path (~1, ~12,.... ?.& = vf) in digraph G

such that x E L(q)L(7$ l l l L(fk-I), where ri is the label of the edge

(Vi, Vi+& i = 1,... , k - 1.

We claim that statement S holds with respect to the graph G at any stage
of the above construction of G(r). First, it is clear that S holds with respect

to the graph G at the beginning of the step 2. Next, we observe that, because

of the way the edges are replaced, if S holds with respect to a graph G, then it
still holds after an edge replacement performed at step 2. Thus, the statement
S holds with respect to the graph G at the end of step 2.

At step 3, we delete edges with the label 0, and this does not affect state-

ment S, since L(0) = 8. Therefore, at the end of step 3, each edge of G(r)

is labeled by exactly one symbol from C U {E}, and statement S implies that

x: E L(r) if and only if there is a path in G(r) from VI to VI whose associated

string is exactly z.^0

Example 1.24 Construct G(r) for r = (11 + O)(OO + l).

Solution. The construction is shown in Figure 1.4.^0

In a digraph G(r), an edge with label E is called an E-edge. For a regular
expression T, it is often desirable to construct G(r) with a minimum number
of E-edges while still preserving the property of Theorem 1.23. For instance,
in Figure 1.4, the two middle E-edges can be replaced by a single E-edge. The
following is a simple rule for eliminating redundant e-edges: