If L is regular, show that even(L) is also regular
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):