Problem Solving in Automata, Languages, and Complexity

56 FINITE AUTOMATA

Figure 2.38: Induction step.

+1> = a% for some il >^0 and, for j = 2,... , k, +Q) is either c or d&b

for some ij > - 0. Or, equivalently, 7$ n) E u* b(c + da* b)’. Conversely, we can

see that, for any regular expression r in a+b(c + du*b)*, there is a path 7r in

G from w1 to of, with Y(T) = T. Thus, it follows that

L(G) = u*b(c+ du*b)*,

and the basis step is proven.

Inductiosz Step: For n > - 1, we can choose a vertex v other than VI and

of and remove it by the following transformation: First, by the method used

in the basis step, we may eliminate multiple edges and assume that there is

at most one edge from any vertex u to any vertex u). Now, assume that v

has a self-loop with label c; that is, G has an edge ‘u & ‘u. We remove v

along with this edge. For any pair (u, w) of vertices in G, with edges u -$ V,

zr -$ w and u + d w, we remove the edges u + ‘u and v + w and replace the

label d of the edge u + w with a new label d + uc*b. (If there was no edge

u -+ w in G, we treat it as having an edge u + w with label 8.) We show this

transformation in Figure 2.38. (To make the figure readable, we omit some

edges from vertices on the left to vertices on the right. We assume that the

edge from the ith vertex on the left to the jth vertex on the right has the label

dij.) Note that this transformation does not change the associated language.

Thus, by the induction hypothesis, the language accepted by G is regular.

The above completes the proof that the languages associated with labelled

digraphs are all regular. Finally, we show that for any NFA M, L(M) is

regular. For any NFA M, we first convert it to an equivalent NFA M’ with

a single final state by changing all final states in M into nonfinal states, and

adding a new final state and a new E-move from each old final state to it

(see Figure 2.39). Now the transition diagram of this NFA M’ is exactly a

labelled digraph G with the property that each edge is labelled by a single

symbol from {E} UC. It is also clear that L(G) = L(W). Thus, by the above

proof, L(W) is a regular language.

We have just proved the following theorem: