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

Question

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?

Answer 1

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

Answer 2

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):

Answer 3

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