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 M0 that recognizes f(B). Consider the machine M0 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.
