commutative language (original) (raw)

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

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

where π is a permutation 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.

The first equivalence comes from the fact that if v⁢y⁢x⁢w is just a permutation of v⁢x⁢y⁢w, and that every permutation on {1,…,n} may be expressed as a product of transpositions. 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={(a⁢b⁢c)n∣n≥0}, then Ψ-1∘Ψ⁢(L)={w∣|w|a=|w|b=|w|c}.

References

• 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).