patternMinor
If L is regular, show that even(L) is also regular
Viewed 0 times
showregularalsothateven
Problem
I am stuck on the following question.
If $L$ is regular show that $\text{even}(L)$ is also regular. Here $\text{even}(L) = \{ \text{even}(w) : w \in L \}$, $\text{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions. For example, if $L=\{0, 01, 02, 0202, 12120\}$, then $\text{even}(L)=\{\epsilon, 1, 2, 22\}$.
How can I prove that $\text{even}(L)$ is also regular?
If $L$ is regular show that $\text{even}(L)$ is also regular. Here $\text{even}(L) = \{ \text{even}(w) : w \in L \}$, $\text{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions. For example, if $L=\{0, 01, 02, 0202, 12120\}$, then $\text{even}(L)=\{\epsilon, 1, 2, 22\}$.
How can I prove that $\text{even}(L)$ is also regular?
Solution
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')).
$$
$$
\operatorname{even}(L) = d(h^{-1}(L) \cap (\Sigma'\Sigma)^*(\epsilon+\Sigma')).
$$
Context
StackExchange Computer Science Q#49342, answer score: 7
Revisions (0)
No revisions yet.