Problem Solving in Automata, Languages, and Complexity

2.6 Closure Properties of Regular Languages 67

alphabets C and F. We observe that C(A, B) = A n C(C, B). From the
third case, we know that C(C, B) is regular. Since A is also regular, we
conclude that C(A, B) is regular. cl

• Example 2.44 Show that if L is regular, so is

Proof. Since L is regular, there exists a DFA A& = (Q, C, S, s, F) accepting L.
For each state q E Q, let A, be the set of strings 2 whose computation path in
M starts from s and ends at q, and B, the set of strings z whose computation
path in M, when started at state q, ends at a final state. That is,

A, = {z E C* 1 S(s,z) = q},

Bq = {z E c* 16(q,z) E F}.

Then, we can see that

SQRT(L) = u b E A, 1 (3~) [IYI = lx12, Y E Bq]}+

qEQ

It is clear that all sets A, and B, are regular. Therefore, by Example 2.43, the
set {z E A, I (3Y) [IYI = ld2, Y (5 &I) is regular for all q E Q. We conclude

that SQRT(L) is also regular. cl

Exercise 2.6

1. Prove the following identity:

(a> MAX(L) = L \ (L/C+), where MAX(L) = {z E L I x is not a

proper prefix of any string in L}.

(b) MIN(L) = L \ (Lx+).

2. For any two bits a, b E (0, l}, a $ b d enotes the exclusive-or of a and b;
   that is, 0 @ 0 = 1 $1 = 0 and 0 $1 = 1 $0 = 1. For any two binary
   strings z and y with 1x1 = 1~1, it: @ y d enotes the bitwise exclusive-or of
   JZ and y. For example, if IX: = 0011 and y = 0101, then J: $ y = 0110.
   Let A = OOl(0 + 1)” and B = (0 + 1)” 100. Find a regular expression for
   each of the following languages:
   (a) A V B.
   (b) A CB B = {z @ y 1 Z.T E A, y E B, 1x1 = 1~1).
   (c) (a1ha2b2 l l l anbn I ala2 l -a, E A, b& l b, E B}.


3. Show that if A and B are regular languages , so are the following lan-
   guages:
   (a) {z 1 mR E A}.