[Solved]: If L is regular show that even (L) is also regular

Problem Detail: 

I am stuck on the following question

If L is regular show that even(L) is also regular

where even(L) = {even(w) : w ∈ L}

w is a string in L

even(w) is the string obtained by extracting from w the letters in even numbered positions

Asked By : Near

Answered By : Yuval Filmus

We can also solve this question using closure operations. Let $\Sigma$ be the original alphabet, and let $\Sigma' = \{x' : x \in \Sigma\}$ be a second copy of the alphabet. Define two homomorphisms $h$ and $d$ by $h(x) = h(x') = x$ for all $x \in \Sigma$ and $d(x) = x$, $d(x') = \epsilon$ for all $x \in \Sigma$. Then $$ \operatorname{even}(L) = d(h^{-1}(L) \cap (\Sigma'\Sigma)^*(\epsilon+\Sigma')). $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49342