Problem Solving in Automata, Languages, and Complexity

2.6 Closure Properties of Regular Languages 63

Figure 2.43: Solution to Example 2.40.

For each states of M, we make two cojes of M: Gi and zi. We connect

all final states of A& to the initial state of Mi with E-edges. For a state qj in M,

we denote the corresponding states in Gi and Ei by 4: and $, respectively.

Now, we create a new initial state s and a new final state f, and connect s

to state 4: for every z; and connect state qi for every zi to f with E-edges.

Also, all final states in zi and Ei are changed to nonfinal states. (See Figure

2.43.)

We let M’ be the resulting NFA, and claim that L(M’) = {my 1 yz E L).

First, if ylz: E L, then there exist states qi E Q and qj E F such that S(qo, y) =

qi and S(qi, z) = qj. Therefore, the following path in M’ accepts zy:

Conversely, we can see that any accepting path in M’ must be of the above

form, with qj f F. Thus, the original DFA accepts yx by the following path:

That means M’ only accepts strings of the form my with yz E L. Cl

• Example 2.41 Show that if L is a regular language, so is

LL 2 = ix I (3Y) [I4 = IYL XY E 4).

Proof 1. Let M = (Q, C, S, qo, F) be a DFA accepting L, with Q = {qo, 41,... ,

qn}. We will construct an NFA accepting Lh. Intuitively, we can simulate M

on x: to decide whether x E LL as follows:

2

2

(1) We nondeterministically guess a final state qj E F and a string y with

IYI = 14

(2) We simulate M, in parallel, on x from qo forward, and on y from qj

backward. (As demonstrated in Example 2.34, we reverse the direction

of the arrows in the transition diagram of M to simulate it backward.)