shuffle of languages

Let $\Sigma$ be an alphabet and $u,v$ words over $\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}\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\{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 $\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. 1.

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

2. 2.

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

3. 3.

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

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

 $\displaystyle u\diamond v$ $\displaystyle=$ $\displaystyle[aba\diamond ba]\{b\}\cup[ab\diamond bab]\{a\}$ $\displaystyle=$ $\displaystyle[(aba\diamond b)\cup(ab\diamond ba)]\{ab\}\cup[(ab\diamond ba)% \cup(a\diamond bab)]\{ba\}$ $\displaystyle=$ $\displaystyle(ab\diamond ba)\{ab,ba\}\cup(aba\diamond b)\{ab\}\cup(a\diamond bab% )\{ba\}$ $\displaystyle=$ $\displaystyle\{abba,baab,abab,baba\}\{ab,ba\}\cup\{baba,abba,abab\}\{ab\}\cup% \{abab,baab,baba\}\{ba\}$ $\displaystyle=$ $\displaystyle\{abba,baab,abab,baba\}\{ab,ba\}$ $\displaystyle=$ $\displaystyle\{abbaab,baabab,ababab,babaab,abbaba,baabba,ababba,bababa\}$

Remark. Some closure properties with respect to the shuffle operation: let $\mathscr{R}$ be the family of regular languages, and $\mathscr{F}$ the family of context-free languages. Then $\mathscr{R}$ is closed under $\diamond$. $\mathscr{F}$ is not closed under $\diamond$. However, if $L_{1}\in\mathscr{R}$ and $L_{2}\in\mathscr{F}$, then $L_{1}\diamond L_{2}\in\mathscr{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 2013-03-22 18:56:16 Last modified on 2013-03-22 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 shuffle-closed Synonym shuffle-closure Related topic PqShuffle Related topic DeletionOperationOnLanguages Related topic InsertionOperationOnLanguages Defines shuffle Defines shuffle closed Defines shuffle closure