i j k
1) L = { a b c  |  i<>j or j<> k}

   Is L regular?


 Well, obviously, no its not, but how do we show that?

a) First lets do something much simpler:

          i i i
  Li = { a b c  }

  Claim Li is regular.
  therefore there must be a DFA with size n, which is the minimal
  accepting automata.
   
            n n n
  Pick z = a b c  


  obviously (given z=uvw and |uv| <= n and |v|>=1)

        j
   v = a

   But, if we pick i to 0,

           0     n-j n n
   then  uv w = a   b c  which is not in Li, so Li is not regular!

 Cool, so we can do a Pumping Lemma problem!.
           
                   
b)  Now, think about L* = a*b*c*.  Obviously, its regular, cause we just
    wrote a regular expression for it.

c)  Now, consider the concept of set difference.  

    Set difference says L1 - L2 = {x | x in L1 but x not in L2 }

    If we have two regular languages (say L1 and L2) then there must be
    DFAs (say M1 and M2) which accept them.
    M1 = (Q1, E1, q0', d1, F1) and M2 = (Q2, E2, q0'', d2, F2)

    Build a new machine:

    M = (Q1xQ2, E1 u E2, [q0',q0''], d, F)
   

    where d([qi',qi''],x) = [qj',qj''] iff d1(qi',x) = qj' and
                                           d2(qi'',x) = qj''

    and F = { [q',q''] | q' in F1, and q'' not in F2 }

   (NB this is exactly the same construction we used for intersection,
    when we wanted strings in both languages, except now we pick
    things in the first, but not the second language).

   L(M) = L1 - L2 for any two regular languages,
   therefore, regular languages are closed under set difference!


So,  since L* is regular,
     L* - L  will produce a regular language if L is regular,
     but since L* - L = Li,
     and we know that Li is not regular,
     then L cannot be regular.

     Proved (using amongst other things, the Pumping Lemma)!

          R
2) L = {xx y | x,y in (0+1)+}


   a) Consider any string z in L, it must have the following structure:

          R
   z = ass ay   (where x = as, s could be empty, or longer; 
                               a is just one character)

   pick u = empty string
        v = a

              R
        w = ss ay

           i
   Claim uv w is in L for any i:

                   0      R
   if i = 0 then uv w = ss ay  which must be in L

                   i     i  R
   if i > 1 then uv w = a ss ay, but then you have more than 1 "a" at the
                                 beginning of the word, and it must be in L.

   So since for every z, I can pick uvw such that for every i,
   
     i
   uv w must be in L, then L has the pumping property.

   NOTE, this does not mean that L has to be regular!  The lemma only
    says that if a language is regular it has the property

   So, basically, the pumping lemma doesn't help much in this case.


   (Looking ahead, it is easy to see that this language is context-free:

   S -> AB
   A -> 0A0 | 1A1 | 00 | 11
   B -> 0B | 1B | 0 | 1

   but every regular language is context-free, so that is also no help!)

                                           R
   b) OTOH, consider this problem Lq = { xx  }

      Claim Lq is regular,
      then there must be a minimal DFA of size n.

                n n n n
      Pick z = 0 1 1 0

                       j
      then  v must be 0

                          0     n-j n n n
      then pick i=0, so uv w = 0   1 1 0  which is obviously not in Lq,
   
      so the pumping property does not apply, therefore Lq is not regular.


    But, notice that Lq = L/(0+1)*

    since (0+1)* is regular, and the regular sets are closed under quotient,
    
    the fact that Lq is not regular, means that L can not be!

    Once again, proved with the assistance of the pumping lemma (and a
    little help from the closure properties).

    I guess that's why this problem was "starred".  Sorry for trying
   to do it on-the-fly during a review!
   

3) check out page 56 (the explanation of the pumping lemma):  

   (0+1)* contains arbitrarily long strings in which no substring appears
   three times consecutively. (proof left as exercise in the book)

   HERE's the idea
   
   consider the following four strings:

   01  011  001  0011

   they can be pasted together in the following four ways:

   010110010011  011001001101  001001101011  001101011001

   none of which have 3 consecutive substrings.

   Further, each of them can be pasted together in four different ways,
   none of them have 3 consecutive substrings either!

   In fact, this can be done continually, just call the four strings you
   get at one level a, b, c, d.  Then you can create four new strings:
 
   abcd bcda cdab dabc
 
   at the next level; each of which is four times as long as the last 
   level, and none of which have 3 consecutive substrings!