Let $\Sigma=\{a,b\}$, $L$ and $R$ be languages over $\Sigma$ and $h:\Sigma^* \to \Sigma^*$ be a homomorphism. Prove or disprove the following statements:
- $h^{-1}(L\cup R)=h^{-1}(L)\cup h^{-1}(R)$
- $L=h^{-1}(h(L))$
$\begin{align} h^{-1}(L\cup R)&=\{x\in\Sigma^*\mid h(x) \in L\cup R\}\\ &=\{x\in\Sigma^*\mid h(x)\in L \lor h(x)\in R\}\\ &=\{x\in\Sigma^* \mid h(x)\in L\}\cup \{x\in\Sigma^*\mid h(x)\in R\}\\ &=h^{-1}(L)\cup h^{-1}(R) \end{align}$
$L=h^{-1}(h(L))$
No, let $L=\{aab,ba,aa,b\}$ and $h(a)=\lambda$, $h(b)=b$, $\left((h(\lambda)=\lambda\right)$. It follows, that $h(L)=\{b,b,\lambda,b\}$ and $h^{-1}(h(L))=\{b,b,\lambda,b\}$, but $L\neq h^{-1}(h(L))$. The statement is not true.
Are both proofs correct? Thank you in advance.
Your solution for (1) is correct.
Your solution for (2) is not correct. With your choice of $h$ and $L$, one has $h(L) = \{b, 1\}$ (where $1$ is the empty word, a better notation when you use monoid homomorphisms, since the empty word is the identity of the monoid $\Sigma^*$). Then $h^{-1}(h(L)) = a^*ba^* + a^* \not = L$.
A much simpler example is to take $h(a) = h(b) = 1$ and $L = \{1\}$. Then $h(L) = \{1\}$ and $h^{-1}(h(L)) = \Sigma^*$.