Prove that the language of squares is not regular using homomorphism

Question

If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular.

Assume that the language $L=\{yy:y \in \{0,1\}^*\}$ is given. Can you provide a homomorphism for $L$ like $h$ that $h(L)$ is not regular?

Note : I don't want a simple homomorphism. I want a good homomorphism that $h(L)$ is obviously not regular. So there should be no need to use pumping lemma to prove that $h(L)$ is not regular. But you can use the pigeonhole principle.

Answer 1

As illustrated by other answer and comments there seems to be no easy way just using morphisms. Still it is a good observation that simple closure properties can be of help. In your case I would suggest intersection with regular languages as a tool: $L\cap 0^*10^*1 = \{0^n10^n1 \mid n\ge 0\}$ whch some recognize immediately as non-regular.

Alternatively one could include morphisms, inverse morphisms and intersection with regular languages (or, equivalently, finite state transductions). With these regularity preserving operations $L$ can be transformed in to $ \{a^nb^n \mid n\ge 0\}$, mother of all non-regular examples.

Answer 2

You can not prove this using homomorphisms only. There are exactly $2^2=4$ functions $\{0,1\} \rightarrow \{0,1\}$. All larger co-domains can be ignored by restricting the function to its image.

These functions are:

1. $h_0 = \{0 \mapsto 1, 1 \mapsto 1\}$: $h(L) = \{(11)^{n}|n\geq 0 \}$ which is regular
2. $h_1 = \{0 \mapsto 1, 1 \mapsto 0\}$: $h(L) = L$
3. $h_2 = \{0 \mapsto 0, 1 \mapsto 1\}$: $h(L) = L$
4. $h_3 = \{0 \mapsto 0, 1 \mapsto 0\}$: $h(L) = \{(00)^{n}|n\geq 0 \}$ which is regular

So, morphism do improve your prove in any way.

Can you provide a homomorphism for L like h that h(L) is not regular?

The answer to this question is "yes", because $L$ is not regular and $h_1$ and $h_2$ map $L$ to $L$.