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

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

• Re: your edit. Changing the transition function $\delta:Q\times \Sigma\to Q$ also works, but the details are slightly different. Note that you use the so-called "extended" transition function on strings instead. If $\delta'$ is the new transition function, then $\delta'(q,\sigma) = \delta(\delta(q,\sigma),\sigma)$. Just as you wrote, except for the trailing string $w$. Apr 26 at 14:19

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)$$.

• what about the words in L that are not in the pattern of duplicate letters? how can i g^-1 them? Apr 26 at 12:34
• their $g^{-1}$ will be the empty set, hence they are not contributing to the language. Notice that also in your definition of $shrink$ this is the case. Apr 26 at 13:54