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