# an operation which turns a non-regular language into a regular one

In the morning I got a very interesting problem:

Define $shuff(L) = \{w0v | wv \in L\}$. If shuff(L) is regular, prove or disprove L is also regular.

Update. The original problem is at http://www.student.cs.uwaterloo.ca/~cs462/prob4.pdf

At first glance, it’s not told whether 0 is in the alphabet of L. So there are two cases.

If 0 isn’t in the alphabet of L, then it’s easy. A homomorphism $h(0) = \epsilon$ will turn shuff(L) into L. So L must be regular.

If 0 is in the alphabet of L, then things are a little bit difficult. It took me several hours (including the sleeping time…) to find an instance that will disprove this proposition.

From now on we suppose the alphabet is {0,1}. Take L to be the complement of $\{0^n1^n0^n1^n | n > 0\}$. Of course $\overline{L}$ is non-regular. So is L, since regularity is closed under complement. But $shuff(L) = \{w | w$ contains at least one 0 $\}$, which is regular.

To see $shuff(L) = \{w | w$ contains at least one 0 $\}$, we must show $shuff(L) \subseteq \{w | w$ contains at least one 0 $\}$ and $\{w | w$ contains at least one 0 $\} \subseteq shuff(L)$. The first direction is trivial. To show the second direction, for any w in this language, we can eliminate one 0 (there must be at least one 0) and get w’. If w’ is in L, then $w \in shuff(L)$. If w’ isn’t in L, then w’ must be in $\overline{L} = \{0^n1^n0^n1^n | n > 0\}$. But for any $w’ \in \overline{L}$, $shuff(w’) = shuff(x’)$ for a particular $x’ \in L$ (the key of the proof but not hard to prove). So $w = shuff(w’) = shuff(x’) \in shuff(L)$. This completes the proof.