2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ A very elegant solution to the problem! Thank you. $\endgroup$ – Anton Trunov Nov 11 '15 at 18:03
3
$\begingroup$

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

DFA accepting the same language as (001)*

Here is our product $\epsilon$-NFA accepting even(L):

epsilon-NFA accepting even(L)

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.