1. Suppose you are given a homomorphism f() from alphabets S to T. Given a DFA D=, construct another NFA/DFA M= such that M accepts x iff D accepts f(x). Hint: Assume that F = {qf}. Now, write down LHS and RHS using extended tr. functions. 2. Define FATTEN(a) = 10 and FATTEN(b)=20, and for any other string w=w1 w2 ... wk, FATTEN(w)=FATTEN(w1).FATTEN(w2) ... FATTEN(wk). Show that regular languages are closed under INVFATTEN(L) = { x: there is some y in L such that FATTEN(y)=x}. Hint: Use homomorphism. ========== Part B ========= 3. Find regex for these languages: (a) { w : w starts with 0 and has odd length, or starts with 1 and has even length} (b) { w : w is any string except 11 and 111 } (c) { w : w contains an even number of 0s, or contains exactly two 1s} (d) reverse of the language matched by the regex (aab U bbaba)*baba 4. Give a recursive definition of a "reverse" operation of a regex R that matches the reverse of the strings matched by R. Now prove that L(reverse(R))=reverse(L(R)). Use this to prove that regular languages are closed under Reverse(). 5 (for later). Prove that { 0^2n 1^n : n >= 0} is not regular using homomorphism and known facts. Hint: Regular languages are closed under inverse homomorphism.