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.

$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

$\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