Closure of regularity under the action of replacing identical pairs of letters

Question

Given any regular language L, we define $$shrink(L) = \{ \sigma_{1}\sigma_{2}\sigma_{3}...\sigma_{n} : \sigma_{1}\sigma_{1}\sigma_{2}\sigma_{2}\sigma_{3}\sigma_{3}...\sigma_{n}\sigma_{n} \in L \} $$

The question is whether these languages are regular or not.

The intuition says they are, and I was thinking about proving it with Homomorphism, i.e defining homomorphism from shrink(L) by duplicating each word and then proving that $h(shrink(L))$ is regular therefore shrink(L) is regular.

But I'm not exactly sure how to do it properly..

edit: another idea I had is by using DFA - if L is regular it has a DFA called M, so I can build M' by changing Delta such that $\delta (q,\sigma w) = \delta(\delta(q,\sigma w),\sigma w)$. Will it work?

Thanks for any help

Answer 1

You can do it using homeomorphism. Define $h:\Sigma\rightarrow \Sigma^*$ by: $h(\sigma)=\sigma\sigma$.

Then, $h$ induces a homeomorphism $g$ that is defined by $g(\sigma_1,\dots,\sigma_n)=h(\sigma_1)\dots h(\sigma_n)$.

Then, its easy to see that $shrink(L)=g^{-1}(L)$ (prove this!). From closure properties of regular languages we know that $g^{-1}(L)$ is regular, hence also $shrink(L)$.