commutative language


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

u=a1an

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

aπ(1)aπ(n),

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

n!n1!nm!

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

{v|v|a=|u|a,aΣ}.

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.

References

  • 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