# Homomorphism Languages

Let $h$ be a homomorphism and let $L$ be a language. Writing ${}^*$ for Kleene star, I want to show that $(h^{-1}(L))^* \neq h^{-1}(L^*)$. Can I prove this just by showing that we can have $h^{-1}(L)$ to be empty (because no strings are mapping into $L$) and therefore the right side is the empty set? Doing the same to the left side gives $\emptyset^* = \{\epsilon\}\neq\emptyset$.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – D.W. Oct 7 '15 at 23:47
• I'm not sure what you mean by "we can have $h^{−1}(x)$ which does not have a map in $L$". Could you try to explain? – David Richerby Oct 8 '15 at 14:16

Unfortunately both sides contain the empty string. As you say, the Kleene star of the empty set also contains the empty string: $\varnothing^* = \{ \lambda\}$. The Kleene star of a language $L$, equals $L^* = \cup_{i\ge 0} L^i$, where $L^0 = \{\lambda\}$ and $L^i = L \cdot L^{i-1}$ for $i\ge 1$.
On the other hand $h(\lambda) = \lambda$ for any morphism $h$, so $\lambda \in h^{-1}(K)$ whenever $\lambda \in K$. As $L^*$ contains the empty string this is the case here.
However, this does not mean the two sets are equal. Consider $h:\{a,b\}^*\to \{a\}^*$ defined by $h(a) = a$ and $h(b) = aa$ and $L=\{a\}$.