Given that $L$ is a regular language over some alphabet $\Sigma,$ prove that the language $L'=\{x_1x_2\cdots x_k\ |\ x_1,\dots ,x_k \in \Sigma\ \land \exists y_1,y_2,\dots y_{2k} \in \Sigma , \ x_1y_1y_2x_2y_3y_4 \cdots x_ky_{2k-1}y_{2k} \in L\}$ is regular.

My thoughts:

Let $M_1=(Q,\Sigma,\delta,q_0,F)$ be a DFA accepting L.

I was trying to simulate three steps in $M_1:$ one with respect to $\sigma$ and two that we can guess any two characters from the alphabet.

Let $M_2 = (Q,\Sigma,\delta',\{q_0\},F)$ be a NFA, where: $\forall q \in Q, \sigma \in \Sigma: \delta'(q,\sigma)=\{\delta(\delta(\delta(q,\sigma),a),b)|a,b\in\Sigma\}$

I'm not sure how to continue and prove that $L(N)=L',$ that is $w \in L(N) \iff w\in L'.$

Any lead on how to continue or another way to approach to problem is appreciated.


A substitution $\sigma: A^* \to B^*$ is defined by choosing, for each letter $a \in A$, a language $\sigma(a)\subseteq B^*$, and by setting $\sigma(1) = 1$ and $\sigma(a_1 \dotsm a_n) = \sigma(a_1) \dotsm \sigma(a_n)$ for each word $a_1 \dotsm a_n$.

Now, if $\sigma: A^* \to B^*$ is a substitution and $R$ is a regular language of $B^*$, then the language $$ R' = \{u \in A^* \mid \sigma(u) \cap R \not= \emptyset\} $$ is regular. Your question corresponds to the special case where $A = B = \Sigma$ and $\sigma(a) = aAA$ for every $a \in A$.


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.