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 $\mathcal{R}$ be the family of regular languages, and $\mathcal{F}$ the family of contextfree languages. Then $\mathcal{R}$ is closed under $\diamond $. $\mathcal{F}$ is not closed under $\diamond $. However, if ${L}_{1}\in \mathcal{R}$ and ${L}_{2}\in \mathcal{F}$, then ${L}_{1}\diamond {L}_{2}\in \mathcal{F}$. The proofs of these closure properties can be found in the reference.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Title  shuffle of languages 
Canonical name  ShuffleOfLanguages 
Date of creation  20130322 18:56:16 
Last modified on  20130322 18:56:16 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 68Q45 
Synonym  shuffle product 
Synonym  shuffleclosed 
Synonym  shuffleclosure 
Related topic  PqShuffle 
Related topic  DeletionOperationOnLanguages 
Related topic  InsertionOperationOnLanguages 
Defines  shuffle 
Defines  shuffle closed 
Defines  shuffle closure 