commutative language

Let Σ be an alphabet and u a word over Σ. Write u as a productMathworldPlanetmathPlanetmath of symbols in Σ:


where aiΣ. A of u is a word of the form


where π is a permutationMathworldPlanetmath on {1,,n}. The set of all permutations of u is denoted by com(u). If Σ={b1,,bm}, it is easy to see that com(u) has


elements, where ni=|u|bi, the number of occurrences of bi in u.

Define a binary relationMathworldPlanetmath on Σ* by: uv if v is a permutation of u. Then is a congruence relationPlanetmathPlanetmath on Σ* with respect to concatenationMathworldPlanetmath. In fact, Σ*/ is a commutative monoid.

A languagePlanetmathPlanetmath L over Σ is said to be commutativePlanetmathPlanetmathPlanetmath if for every uL, we have com(u)L. Two equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath characterization of a commutative language L are:

  • If u=vxywL, then vyxwL.

  • Ψ-1Ψ(L)L, where Ψ is the Parikh mapping over Σ (under some ordering).

The first equivalence comes from the fact that if vyxw is just a permutation of vxyw, and that every permutation on {1,,n} may be expressed as a product of transpositionsMathworldPlanetmath. The second equivalence is the realization of the fact that com(u) is just the set


We have just seen some examples of commutative closed langauges, such as com(u) for any word u, and Ψ-1Ψ(L), for any language L.

Given a language L, the smallest commutative language containing L is called the commutative closure of L. It is not hard to see that Ψ-1Ψ(L) is the commutative closure of L.

For example, if L={(abc)nn0}, then Ψ-1Ψ(L)={w|w|a=|w|b=|w|c}.

Remark. The above example illustrates the fact that the families of regular languages and context-free languages are not closed underPlanetmathPlanetmath 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).
Title commutative language
Canonical name CommutativeLanguage
Date of creation 2013-03-22 18:56:56
Last modified on 2013-03-22 18:56:56
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 5
Author CWoo (3771)
Entry type Definition
Classification msc 68Q70
Defines commutative
Defines commutative closure