Homework Exercise 6

Due: by 10am on Thu 27 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. For each regular expression R below, state whether or not the string 010 belongs to L(R), and explain why.

    1. (ε+1)0*1*0

    2. 0(11)*0

    3. (0*1*)*

    4. (0+1)(0*+1*)

  2. For each language Li below, give a reg.exp. Ri such that L(Ri) = Li and a F.S.A. Ai such that L(Ai) = Li. Briefly explain why your answers are correct (i.e., show your work and reasoning).

    1. L1 = { s ∈ {a,b}* : s contains the substring bb }

    2. L2 = { s ∈ {a,b}* : s does not contain the substring bb }