A homomorphism is a function f : from one alphabet to strings over another alphabet. We can extend f to operate on strings by defining f(w) = f(w1)f(w2) f(wn), where w = w1w2 wn and each wi . We further extend f to operate on languages by defining f(A) = {f(w)| w A}, for any language A.

a. Show, by giving a formal construction, that the class of regular languages is closed under homomorphism. In other words, given a DFA M that recognizes B and a homomorphism f, construct a finite automaton M that recognizes f(B). Consider the machine M that you constructed. Is it a DFA in every case?

b. Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.

1.66 A bomomorpbism is a function f: from one alphabet to strings over another alphabet. We can extend f to operate on strings by defining f(w) = f(w1)/(w2) . . . f(wn), where w = wiw2 wn and each wi E . We further extend f to operate on languages by defining f(A) = {f(w)I w E A), for any language A. a. Show, by giving a formal construction, that the class of regular languages is closed under homomorphism. In other words, given a DFA M that rec- ognizes B and a homomorphism f, construct a finite automaton M that recognizes f(B). Consider the machine M that you constructed. Is it a DFA in every case? b. Show, by giving an example, that the class of non-regular languages is not closed under homomorphism