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

I am stuck on the following question.

If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions.

How can I prove that $\mathrm{even}(L)$ is also regular?

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')).$$

• A very elegant solution to the problem! Thank you. – Anton Trunov Nov 11 '15 at 18:03

1) Since $L$ is regular we can build a DFA $M = (Q,\Sigma,\delta,q_0,F)$ accepting it.

2) Next we build a DFA $C = (\{c_0,c_1\},\Sigma,\delta_c,c_0,\{c_0\})$ that accepts all strings of even length -- it will help us "count". I'll let you figure out $\delta_c$.

3) Make a product $\epsilon$-DFA $P = (Q_p,\Sigma,\delta_p,(q_0,c_0),F_p)$ from $M$ and $C$, where

$$Q_p = Q \times \{c_0,c_1\}$$

Accepting states are just all state pairs, with an accepting state from the original DFA $M$: $$F_p = \{(q_i,c_j) \mid (q_i,c_j) \in Q_p \wedge ~q_i \in F \}$$ And the transition function looks like this:

• all transitions from the "even" state pairs $(q_i,c_0)$ are replaced by $\epsilon$-transitions: $$\begin{array}{ll} \delta_p((q, c_0),~a) = \emptyset,~\forall a \in \Sigma,~\forall q \in Q\\ \delta_p((q, c_0),~\epsilon) = \{(\delta(q,a),~c_1) \mid a \in \Sigma\},~\forall q \in Q \end{array}$$
• all transitions from the "odd" state pairs $(q_i,c_1)$ mimic the original DFA $M$ (or more precisely, unmodified product automaton): \begin{array}{ll} \delta_p((q, c_1),~a) = \{(\delta(q,a),~c_0)\},~\forall a \in \Sigma,~\forall q \in Q \\ \delta_p((q, c_1),~\epsilon) = \emptyset,~\forall q \in Q \end{array}

Intuitively, the $\epsilon$-NFA $P$ works as follows: it guesses (or skips) all the odd-numbered symbols in the input string.

We have got an $\epsilon$-NFA accepting even(L), thus even(L) is regular.

Example. Let our original automaton be a DFA which accepts the same language L as the regular expression $(001)^*$ (dead states are not shown): Here is our product $\epsilon$-NFA accepting even(L): Let $$(Q,\Sigma,\delta,q_0,F)$$ be a DFA for $$L$$. Define a NFA with ε-moves $$D=(Q \times \{0,1\} , \Sigma, \delta', (q_0, 0), F\times \{0,1\})$$ where the transitions (not into the empty set) are:

• $$\delta'((q,0),\epsilon) = \{ (\delta(q,\sigma),1) \mid \sigma \in \Sigma\}$$.
• $$\delta'((q,1),\sigma) = \{ (\delta(q,\sigma),0)\}$$.

It is immediate that $$\sigma_1\sigma_2\cdots\sigma_k$$ is accepted by $$D$$ if and only if there are $$\mu_1, \mu_2, \cdots, \mu_k\in \Sigma$$ and $$\mu_{k+1}\in\{\epsilon\}\cup\Sigma$$ such that $$\mu_1\sigma_1\mu_2\sigma_2\cdots\mu_k\sigma_k\mu_{k+1}\in L$$.

(The above straightforward construction is easier for me to understand. If you find this answer too brief, you may want to look at Anton's answer for more details and explanations.)