patternMinor
Prove that the language of squares is not regular using homomorphism
Viewed 0 times
thehomomorphismregularsquareslanguageprovethatusingnot
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#55618, answer score: 3
Revisions (0)
No revisions yet.