commutative language

Let $\mathrm{\Sigma }$ be an alphabet and $u$ a word over $\mathrm{\Sigma }$. Write $u$ as a product of symbols in $\mathrm{\Sigma }$:

$$u=a_1\mathrm{\cdots }{a}_n$$

where $a_i\in \mathrm{\Sigma }$. A of $u$ is a word of the form

$$a_{\pi (1)}\mathrm{\cdots }{a}_{\pi (n)},$$

where $\pi$ is a permutation on $\{1,\mathrm{\dots },n\}$. The set of all permutations of $u$ is denoted by $\mathrm{com}(u)$. If $\mathrm{\Sigma }=\{b_1,\mathrm{\dots },b_m\}$, it is easy to see that $\mathrm{com}(u)$ has

$$\frac{n!}{n_1!\mathrm{\cdots }{n}_m!}$$

elements, where $n_i={|u|}_{b_i}$, the number of occurrences of $b_i$ in $u$.

Define a binary relation $\sim$ on ${\mathrm{\Sigma }}^{*}$ by: $u\sim v$ if $v$ is a permutation of $u$. Then $\sim$ is a congruence relation on ${\mathrm{\Sigma }}^{*}$ with respect to concatenation. In fact, ${\mathrm{\Sigma }}^{*}/\sim$ is a commutative monoid.

A language $L$ over $\mathrm{\Sigma }$ is said to be commutative if for every $u\in L$, we have $\mathrm{com}(u)\subseteq L$. Two equivalent characterization of a commutative language $L$ are:

• If $u=vxyw\in L$, then $vyxw\in L$.

• ${\mathrm{\Psi }}^{-1}\circ \mathrm{\Psi }(L)\subseteq L$, where $\mathrm{\Psi }$ is the Parikh mapping over $\mathrm{\Sigma }$ (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,\mathrm{\dots },n\}$ may be expressed as a product of transpositions. The second equivalence is the realization of the fact that $\mathrm{com}(u)$ is just the set

$$\{v\mid {|v|}_a={|u|}_a,a\in \mathrm{\Sigma }\}.$$

We have just seen some examples of commutative closed langauges, such as $\mathrm{com}(u)$ for any word $u$, and ${\mathrm{\Psi }}^{-1}\circ \mathrm{\Psi }(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 ${\mathrm{\Psi }}^{-1}\circ \mathrm{\Psi }(L)$ is the commutative closure of $L$.

For example, if $L=\{{(abc)}^n\mid n\ge 0\}$, then ${\mathrm{\Psi }}^{-1}\circ \mathrm{\Psi }(L)=\{w\mid {|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 under commutative closures. However, it can be shown that the families of context-sensitive languages and type-0 languages are closed under commutative closures.