Assume we apply the following operation on the regular language $L$:

$$OP(L)=\{a_2a_1a_4a_3\dots a_{2n}a_{2n-1}:a_1a_2a_3\dots a_{2n}\in L\}$$

Why $OP(L)$ remains regular?

I think this is as the same as shuffle but I have no idea to show that.


1 Answer 1


Make a DFA $D$ for language $L$.

Now make a copy $D'$ of this DFA, but only of the states, removing the transitions.

To add back transitions we check for all possible symbols $a, b$ for all possible pairs of states $x, y$ if $\delta(\delta(x, a), b) = y$ in $D$. If so, we add a new non-accepting state $s'$ to $D'$, and the transitions $\delta(x', b) = s'$, $\delta(s', a) = y'$.

We've now ensured that $D'$ recognizes $a_2a_1a_4a_3\dots$ iff $D$ recognizes $a_1a_2a_3a_4$, thus $OP(L)$ must also be regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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