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
