## You are here

Homeshuffle of languages

## Primary tabs

# 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).

## Mathematics Subject Classification

68Q70*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections