shuffle of languages
Let be an alphabet and words over . A shuffle of and can be loosely defined as a word that is obtained by first decomposing and into individual pieces, and then combining (by concatenation) the pieces to form , in a way that the order of the pieces in each of and is preserved.
More precisely, a shuffle of and is a word of the form
where and . In other words, a shuffle of and is either a -insertion of either into or into , for some positive integer .
The set of all shuffles of and is called the shuffle of and , and is denoted by
Clearly, . We shall also identify and with and respectively.
A language is said to be shuffle closed if . Clearly is shuffle closed, and arbitrary intersections shuffle closed languages are shuffle closed. Given any language , the smallest shuffle closed containing is called the shuffle closure of , and is denoted by .
For example, suppose , . Then
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 and , then . The proofs of these closure properties can be found in the reference.
- 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
|Title||shuffle of languages|
|Date of creation||2013-03-22 18:56:16|
|Last modified on||2013-03-22 18:56:16|
|Last modified by||CWoo (3771)|