Homework Exercise 5

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 L1, L2 over alphabet {a,b,c} such that L1.L2 = L2.L1, and briefly justify that each of your pair of languages has this property.