Consider a generalization of a homomorphism, where we define a non- deterministic homomorphism h to be a function from an alphabet to sets of strings over an alphabet T. For example, consider = {0,1}, and T = {a,b}, where h(0) = {a,aa} andh(1) = {,b}. For any language L , we define h(L) T to be all strings over T that can be obtained by starting with a string w L and replacing each 0 in w with one of {a, aa} and replacing each 1 in w with one of {,b}. Note that our choices do not need to be consistent - we can replace some 0s with a and others with aa, etc. If L is regular, does it follow that h(L) is regular as well? If so, provide a proof. If not provide a counterexample (and prove that in your example L is regular and h(L) is not).

Problem 3* [20 pts] Consider a generalization of a homomorphism, where we define a "on- deterministic homomorphism" h to be a function from an alphabet to sets of strings over an alphabet T. For example, consider -(0,1), and T = {a,b}, where h(0)-(a, aa) and h(1) {c, b). For any language L C *, we define h(L) C T* to be all strings over T, that can be obtained by starting with a string w L and replacing each 0 in w with one of {a, aa) and replacing each 1 in w with one of e, b. Note that our choices do not need to be consistent - we can replace some 0's with a and others with aa, etc. If L is regular, does it follow that h(L) is regular as well? If so, provide a proof. If not provide a counterexample (and prove that in your example L is regular and h(L) is not)