shuffle of languages

Let $\mathrm{\Sigma }$ be an alphabet and $u,v$ words over $\mathrm{\Sigma }$. A shuffle $w$ of $u$ and $v$ can be loosely defined as a word that is obtained by first decomposing $u$ and $v$ into individual pieces, and then combining (by concatenation) the pieces to form $w$, in a way that the order of the pieces in each of $u$ and $v$ is preserved.

More precisely, a shuffle of $u$ and $v$ is a word of the form

$$u_1{v}_1\mathrm{\cdots }{u}_k{v}_k$$

where $u=u_1\mathrm{\cdots }{u}_n$ and $v=v_1\mathrm{\cdots }{v}_n$. In other words, a shuffle of $u$ and $v$ is either a $k$-insertion of either $u$ into $v$ or $v$ into $u$, for some positive integer $k$.

The set of all shuffles of $u$ and $v$ is called the shuffle of $u$ and $v$, and is denoted by

$$u\diamond v.$$

The shuffle operation can be more generally applied to languages. If $L_1,L_2$ are languages, the shuffle of $L_1$ and $L_2$, denoted by $L_1\diamond L_2$, is the set of all shuffles of words in $L_1$ and $L_2$. In short,

$$L_1\diamond L_2=\bigcup \{u\diamond v\mid u\in L_1,v\in L_2\}.$$

Clearly, $u\diamond v=\{u\}\diamond \{v\}$. We shall also identify $L\diamond u$ and $u\diamond L$ with $L\diamond \{u\}$ and $\{u\}\diamond L$ respectively.

A language $L$ is said to be shuffle closed if $L\diamond L\subseteq L$. Clearly ${\mathrm{\Sigma }}^{*}$ is shuffle closed, and arbitrary intersections shuffle closed languages are shuffle closed. Given any language $L$, the smallest shuffle closed containing $L$ is called the shuffle closure of $L$, and is denoted by $L^{\diamond }$.

It is easy to see that $\diamond$ is a commutative operation: $u\diamond v=v\diamond u$. It is also not hard to see that $\diamond$ is associative: $(u\diamond v)\diamond w=u\diamond (v\diamond w)$.

In addition, the shuffle operation has the following recursive property: for any $u,v$ over $\mathrm{\Sigma }$, and any $a,b\in \mathrm{\Sigma }$:

1. $u\diamond \lambda =\{u\}$,

2. $\lambda \diamond v=\{v\}$,

3. $ua\diamond vb=(ua\diamond v)\{b\}\cup (u\diamond vb)\{a\}$.

For example, suppose $u=aba$, $v=bab$. Then

$u\diamond v$$=$$[aba\diamond ba]\{b\}\cup [ab\diamond bab]\{a\}$

$=$$[(aba\diamond b)\cup (ab\diamond ba)]\{ab\}\cup [(ab\diamond ba)\cup (a\diamond bab)]\{ba\}$

$=$$(ab\diamond ba)\{ab,ba\}\cup (aba\diamond b)\{ab\}\cup (a\diamond bab)\{ba\}$

$=$$\mathrm{\{}abba,baab,abab,baba\}\{ab,ba\}\cup \{baba,abba,abab\}\{ab\}\cup \{abab,baab,baba\}\{ba\}$

$=$$\mathrm{\{}abba,baab,abab,baba\}\{ab,ba\}$

$=$$\mathrm{\{}abbaab,baabab,ababab,babaab,abbaba,baabba,ababba,bababa\}$

Remark. Some closure properties with respect to the shuffle operation: let $ℛ$ be the family of regular languages, and $ℱ$ the family of context-free languages. Then $ℛ$ is closed under $\diamond$. $ℱ$ is not closed under $\diamond$. However, if $L_1\in ℛ$ and $L_2\in ℱ$, then $L_1\diamond L_2\in ℱ$. The proofs of these closure properties can be found in the reference.