Let $\Sigma = \{a, b\}$. For every language $L \subseteq \Sigma^*$ we denote $\widetilde{L} := \{xy \mid xxy\in L\}$. Prove that if $L$ is regular, then so is $\widetilde{L}$. I tried playing around with the automaton for $L$ and extending it in ways, but I always keep adding unwanted words to the new language and therefore get a language actually bigger than $\widetilde{L}$. I also thought about somehow employing the Myhill-Nerode theorem and the finite equivalence classes of $\approx_L$, but I couldn't rerally figure out an useful way of doing it... Any help is welcome!

  • 1
    $\begingroup$ cs.stackexchange.com/q/41281/755 $\endgroup$
    – D.W.
    Commented Jun 22, 2021 at 7:41
  • $\begingroup$ Wow, okay, that was much heavier than expected... $\endgroup$
    – D. Petrov
    Commented Jun 22, 2021 at 8:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.