Problem Solving in Automata, Languages, and Complexity

88 FINITE AUTOMATA

w Show that the set of all strings over r that represent correct

tiplication, with the second mu1 t ipli .er equal to 3, is regular.

4. Is it true that for any regular language L over {O,l}, the set N(L) =
   { O#“(“) l#l(“) 1 x E L} is also regular? Prove your answer.


5. Prove the following stronger form of the pumping lemma: For any regu-
   lar language L and any positive integer k, there exists a positive integer
   s such that any string II: in L with 1x1 > s can be decomposed into
   X = uvw such that Iv1 > I% and for any i > 0, - uviw E L.

• 
  
  
  
  6. Find a regular language L such that
  
  
  
  

2 = {xz 1 (3~) [lx1 = 1~1 = Izl and xyxy E L]}

is not regular.

7. Let A and B be regular sets over alphabet C. Which of the following
   languages, if any, are necessarily regular?
   (a) {x I x E A and xR E B}.
   (b) {x I x E A and xR @ B}.
   (c) {x I x = xR and x E A}.

• (d) {a~b~a2bn-la&,-+2 l l l anbl I ai, bi E C for 1 < i < - - n, ala2 l l a, E
  A, blb2 l l l b, E B).
  (e) {ala,a2a,-la3a,-2 l **a,al I ai E C for^1 - < i < - 72,
  ala2 l l -a, E A}.
  
  
  • (f) {al a2n a3 a2n-2 a5 a2n-4 ’ ’ ’ U2n-1 a2 I ai E C for 1 5 i 5 272,
    ala2 l =* a, E A}.
  
  
  
  

8. Consider the language

L = {xo”yl”z I x E P, y E Q, 2 E R},

where P, Q and R are nonempty sets over alphabet (0, 1). Can you find

regular sets P, Q, R such that L is not regular? Can you find regular

sets P, Q, R such that L is regular? What if P, Q, R must be infinite

regular sets?

* 9. (a) Is the language {03m+4n I m., n > 0) regular? Prove your answer.

(b) Let L be a language over alphabet (0). Show that L* is regu-

lar. [Hint: Prove and use the fact that if a and b are relatively

prime natural numbers, then for any integer n > - ab, there exist

nonnegative integers u and v such that n = ua + vb.]