(a) Construct deterministic finite automata accepting the following languages: (i) {w {0,1}*/ w is not in the regular language defined by 0*1*}; [2] (ii) {w E {0,1}*| w has an even number of 0's or an odd number of ls} (pay attention to or in this definition); [2] (iii) {W {0,1}*|wends with a subword 01, i.e., w = x01 for some word x}. [2] (b) Let h : {0,1}* + {a,b}* be the function defined by h(e) = e, h(0) = aa and h(1) = b, and for words of length two or greater: = h(aja2 ... An) = h(ai)h(a2)...h(an) for n > 2 and a {0,1}. For a language L {0, 1}* we define h(L) = {h(w)|W E L} {a,b}* For each of the following languages, give a regular expression over {a,b} that corresponds to h(L): (i) L {01" |m, n >0}. [3] (ii) L = {w {0,1}*|w contains 010 as a subword}. [3] (c) Is it possible to write regular expressions representing the following languages over the alphabet {a,b}? If yes, write the regular expression, or else prove that it is impossible. (i) {wwR| W {a,b}*}. Here wR stands for the reverse of the word w. [4] (ii) {ayn-1|n=1,2,...}. [4] =