Let $\Sigma$ be an alphabet and $u$ a word over $\Sigma$ . Write $u$ as a product of symbols in $\Sigma$ : $$u=a_1 \cdots a_n$$ where $a_i \in \Sigma$ . A permutation of $u$ is a word of the form $$a_{\pi(1)} \cdots a_{\pi(n)},$$ where $\pi$ is a permutation on $\lbrace 1,\ldots, n\rbrace$ . The set of all permutations of $u$ is denoted by $\operatorname{com}(u)$ . If $\Sigma =\lbrace b_1,\ldots, b_m\rbrace$ , it is easy to see that $\operatorname{com}(u)$ has $$\frac{n!}{n_1! \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 $\Sigma^*$ by: $u\sim v$ if $v$ is a permutation of $u$ . Then $\sim$ is a congruence relation on $\Sigma^*$ with respect to concatenation. In fact, $\Sigma^*/\sim$ is a commutative monoid.

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

• If $u=vxyw \in L$ , then $vyxw \in L$ .
• $\Psi^{-1}\circ \Psi(L)\subseteq L$ , where $\Psi$ is the Parikh mapping over $\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 $\lbrace 1,\ldots, n\rbrace$ may be expressed as a product of transpositions. The second equivalence is the realization of the fact that $\operatorname{com}(u)$ is just the set $$\lbrace v\mid |v|_a = |u|_a, a\in \Sigma \rbrace.$$

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

For example, if $L=\lbrace (abc)^n \mid n\ge 0\rbrace$ , then $\Psi^{-1}\circ \Psi(L) = \lbrace w\mid |w|_a=|w|_b = |w|_c\rbrace$ .

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.

Bibliography

1

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