Problem Solving in Automata, Languages, and Complexity

2.5 Finite Automata and Regular Expressions 55

8

a+b

Figure 2.36: Multiple edges can be removed.

d

(1) (2)

Figure 2.37: Basis step.

an NFA. In fact, we will prove this result on the labelled digraphs introduced

in Section 1.3.

Recall that a labelled digraph G is a digraph with two special vertices, the

initial vertex ~1 and the final vertex wf, in which each edge is labelled by a

regular expression. For each path 7r from vl to vf in such a digraph G, we let

r(r) be the regular expression associated with n; that is, if r is

then T(X) = ~1~2. l q. Then, for each labelled digraph G, we let

L(G) = U(LW) I x is a path from ~1 to vf }.

We now show, by induction on the number of vertices in G other than vr and

vf , that for each labelled digraph G, L(G) is a regular set.

Basis Step: For n = 0, the digraph G has only two vertices w1 and vf,

or only one vertex 211 = vf. We first eliminate all multiple edges in G by

combining multiple edges with labels ~1, ~2,... , TV from a vertex u to a vertex

v into a single edge from u to w with the label ~1 + r2 +. l l + rm (see Figure

2.36). Then, the resulting digraph are of two types, as shown in Figure 2.37,

in which a, b, c, d denote four regular expressions.

It is clear that a type (1) digraph G has L(G) = a*. For a type (2) digraph

G, consider a path 7r from vr to vf. Assume that 7r passes through wf for

k > - 1 times. Then, we can write 7r as 7rr7r2 l l l rk, where ~1 is a path from

v1 to q, and 7r2,..., TI, are paths from vf to vf, with vf not occurring as

an intermediate vertex in any path q, 1 < _ j < _ k. Then, it is clear that