Let $\Sigma$ be an alphabet and $u,v$ words over $\Sigma$ . A suffle $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_1v_1\cdots u_k v_k$$ where $u=u_1\cdots u_n$ and $v=v_1\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 \lbrace u \diamond v \mid u\in L_1, v\in L_2 \rbrace.$$

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

A language $L$ is said to be shuffle closed if $L\diamond L\subseteq L$ . Clearly $\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 $\Sigma$ , and any $a,b\in \Sigma$ :

1. $u \diamond \lambda = \lbrace u \rbrace$ ,
2. $\lambda \diamond v = \lbrace v \rbrace$ ,
3. $ua \diamond vb = (ua \diamond v)\lbrace b\rbrace \cup (u\diamond vb)\lbrace a\rbrace$ .

For example, suppose $u=aba$ , $v=bab$ . Then \begin{eqnarray*} u\diamond v &=& [aba \diamond ba]\lbrace b\rbrace \cup [ab \diamond bab]\lbrace a\rbrace \\ &=& [(aba \diamond b) \cup (ab \diamond ba) ]\lbrace ab\rbrace \cup [(ab \diamond ba) \cup (a \diamond bab) ]\lbrace ba\rbrace \\ &=& (ab \diamond ba)\lbrace ab,ba\rbrace \cup (aba\diamond b)\lbrace ab\rbrace \cup (a\diamond bab)\lbrace ba\rbrace \\ &=& \lbrace abba, baab, abab, baba\rbrace \lbrace ab,ba\rbrace \cup \lbrace baba, abba, abab \rbrace \lbrace ab\rbrace \cup \lbrace abab, baab, baba \rbrace \lbrace ba \rbrace \\ &=& \lbrace abba, baab, abab, baba\rbrace \lbrace ab,ba\rbrace \\ &=& \lbrace abbaab, baabab, ababab, babaab, abbaba, baabba, ababba, bababa \rbrace \end{eqnarray*} Remark. Some closure properties with respect to the shuffle operatoin: 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 and , then . The proofs of these closure properties can be found in the reference.

Bibliography

1

M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).