===========================================================================
CSC 236                     Homework Exercise 5                 Winter 2008
===========================================================================

Due:  by 10am on Thu 20 Mar
Worth:  1.5%

For each question, please write your answer carefully.  Keep in mind that
approximately half of the marks for each question will be given purely for
having the correct proof structure, written up clearly and precisely,
irrespective of the correctness of the proof.  Also, make sure that you use
notation and terminology correctly, and that you explain and justify what
you are doing -- marks *will* be deducted for incorrect or ambiguous use of
notation and terminology, and for making incorrect, unjustified, ambiguous,
or vague claims in your solutions.


1.  List the elements of {a,ab}*.  Find a clear, concise way to describe
    strings in this language, i.e., state a predicate P(s) such that P(s)
    is true iff s (- {a,ab}*, for all strings s over alphabet {a,b}.


2.  Find three different examples of a language L over alphabet {a,b,c}
    such that L = L.L, and briefly justify that each of your languages has
    this property.


3.  Find three different examples of a language L over alphabet {a,b,c}
    such that L = L*, and briefly justify that each of your languages has
    this property.


4.  Find three different examples of a pair of languages L_1, L_2 over
    alphabet {a,b,c} such that L_1.L_2 = L_2.L_1, and briefly justify that
    each of your pair of languages has this property.