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

  • $\begingroup$ 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$. $\endgroup$ Apr 26, 2021 at 14:19

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

  • $\begingroup$ what about the words in L that are not in the pattern of duplicate letters? how can i g^-1 them? $\endgroup$
    – Galyoss
    Apr 26, 2021 at 12:34
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Apr 26, 2021 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.