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!



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.