Answer all questions. Unless otherwise stated, all the DFAs and NFAs in this homework use = {0, 1} as the alphabet.

1.

(30 point) For each i=1,2 and 3, compose a regular expression Ri, such that L(Ri) = Ci, where

(a) C1 = {w | w has an odd number of 0s, or, contains exactly three 1s}.

(b) C2 ={w|thelengthofw isatmost5}.

(c) C3 = {w | all strings except the strings }11 and 111.

Give reason(s) to support your answer to each case. The reason(s) given for each case should be concise. Do not use more than three complete sentences for each case.

(20 point) By using the standard standard proceduce as given in Lemma 1.55 (Sipser), construct the NFA Na and Nb such that

L(Na) = L(Ra) and L(Nb) = L(Rb).

where Ra = (0 00) 1+ and Rb = +++.

Show intermediate steps.