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.