===========================================================================
CSC 236           Homework Exercise 5 -- Sample Solutions       Winter 2008
===========================================================================


1.  {a,ab}* = {e} U {a,ab} U {aa,aab,aba,abab} U {aaa,...} U ...
            = {e,a,ab,aa,aab,aba,abab,aaa,aaab,aaba,aabab,...}
    This is almost like {a,b}* (all strings of a's and b's), except
    each 'b' comes with an 'a' in front, i.e., P(s) = s is a string
    of a's and b's where each b is immediately preceded by an a.

    Check that s in {a,ab}* iff P(s), by arguing each direction (this was
    not necessary for this question, provided here for your reference):
    =>  It is obvious that each string in {a,ab}* has property P()
        (every b immediately preceded by an a).
    <=  Moreover, each string where each b is immediately preceded
        by an a belongs to {a,ab}*: the string can be broken up
        into pieces 'ab' (one for each b in the string) with every
        other symbol being 'a'.


2.  (a) L = {}:  L.L = {} = L  (by definition of .)
    (b) L = {e}:  L.L = {e} = L  (by definition of .)
    (c) L = {e,a,aa,aaa,aaaa,...}:
            L.L = {e,a,aa,aaa,aaaa,...} U {a,aa,aaa,aaaa,...}
                  U {aa,aaa,aaaa,...} U ...
                = L


3.  (a) L = {e}:  L* = {e} = L  (by definition of *)
    (b) L = {e,a,aa,aaa,...}:  as above, L* = L
    (c) L = {a,b,c}* = {e,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,...}:
         -  s in L* iff s = s_1.s_2...s_k for some s_1,...,s_k in L,
            but then, s is a sequence of a's, b's, c's, so s in L;
         -  s in L iff s = s_1.s_2...s_k for some s_1...s_k in {a,b,c},
            but then, s in L* because {a,b,c} subset of L*.


4.  (a) L_1 = {}  (then, L_1.L_2 = {} = L_2.L_1 for all L_2)
    (b) L_1 = {e}  (then, L_1.L_2 = L_2 = L_2.L_1 for all L_2)
    (c) L_1 = {a,aaa}, L_2 = {e,aa,aaaa}; then:
            L_1.L_2 = {a,aaa,aaaaa} U {aaa,aaaaa,aaaaaaa}
                    = {a,aaa,aaaaa,aaaaaaa}
                    = {a,aaa} U {aaa,aaaaa} U {aaaaa,aaaaaaa}
                    = L_2.L_1