A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w_{1})f(w_{2})...f(w_{n}),$ where $w = w_{1}w_{2}...w_{n}$ and each $w_{i}\in\sum.$ We further extend $f$ to operate on languages by defining $f(A) = \{f(w)| w ∈ A\},$ for any language $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$?$
- Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.
