shuffle of languages


Let Σ be an alphabet and u,v words over Σ. 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 concatenationMathworldPlanetmath) 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

u1v1ukvk

where u=u1un and v=v1vn. 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

uv.

The shuffle operationMathworldPlanetmath can be more generally applied to languagesPlanetmathPlanetmath. If L1,L2 are languages, the shuffle of L1 and L2, denoted by L1L2, is the set of all shuffles of words in L1 and L2. In short,

L1L2={uvuL1,vL2}.

Clearly, uv={u}{v}. We shall also identify Lu and uL with L{u} and {u}L respectively.

A language L is said to be shuffle closed if LLL. Clearly Σ* is shuffle closed, and arbitrary intersectionsMathworldPlanetmath 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.

It is easy to see that is a commutativePlanetmathPlanetmathPlanetmathPlanetmath operation: uv=vu. It is also not hard to see that is associative: (uv)w=u(vw).

In additionPlanetmathPlanetmath, the shuffle operation has the following recursive property: for any u,v over Σ, and any a,bΣ:

  1. 1.

    uλ={u},

  2. 2.

    λv={v},

  3. 3.

    uavb=(uav){b}(uvb){a}.

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

uv = [ababa]{b}[abbab]{a}
= [(abab)(abba)]{ab}[(abba)(abab)]{ba}
= (abba){ab,ba}(abab){ab}(abab){ba}
= {abba,baab,abab,baba}{ab,ba}{baba,abba,abab}{ab}{abab,baab,baba}{ba}
= {abba,baab,abab,baba}{ab,ba}
= {abbaab,baabab,ababab,babaab,abbaba,baabba,ababba,bababa}

Remark. Some closure properties with respect to the shuffle operation: let be the family of regular languages, and the family of context-free languages. Then is closed under . is not closed under . However, if L1 and L2, then L1L2. 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