===========================================================================
CSC 236                     Homework Exercise 6                 Winter 2008
===========================================================================

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.
    (a) (\epsilon+1)0*1*0
    (b) 0(11)*0
    (c) (0*1*)*
    (d) (0+1)(0*+1*)

2.  For each language L_i below, give a reg.exp. R_i such that L(R_i) = L_i
    and a F.S.A. A_i such that L(A_i) = L_i.  Briefly explain why your
    answers are correct (i.e., show your work and reasoning).
    (a) L_1 = { s (- {a,b}* : s contains the substring bb }
    (b) L_2 = { s (- {a,b}* : s does not contain the substring bb }