where . A of is a word of the form
where is a permutation on . The set of all permutations of is denoted by . If , it is easy to see that has
If , then .
The first equivalence comes from the fact that if is just a permutation of , and that every permutation on may be expressed as a product of transpositions. The second equivalence is the realization of the fact that is just the set
We have just seen some examples of commutative closed langauges, such as for any word , and , for any language .
Given a language , the smallest commutative language containing is called the commutative closure of . It is not hard to see that is the commutative closure of .
For example, if , then .
Remark. The above example illustrates the fact that the families of regular languages and context-free languages are not closed under commutative closures. However, it can be shown that the families of context-sensitive languages and type-0 languages are closed under commutative closures.
- 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
|Date of creation||2013-03-22 18:56:56|
|Last modified on||2013-03-22 18:56:56|
|Last modified by||CWoo (3771)|