Skip to main content
edited tags; edited title
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Prove that the language $L=\{yy:y \in \{0,1\}^*\}$of squares is not regular using homomorphism

Source Link

Prove that the language $L=\{yy:y \in \{0,1\}^*\}$ is not regular using homomorphism

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.