commutative language

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 of $u$ is a word of the form

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

where $\pi$ is a permutation  on $\{1,\ldots,n\}$. The set of all permutations of $u$ is denoted by $\operatorname{com}(u)$. If $\Sigma=\{b_{1},\ldots,b_{m}\}$, 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 $\{1,\ldots,n\}$ 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

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

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=\{(abc)^{n}\mid n\geq 0\}$, then $\Psi^{-1}\circ\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.

References

• 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Title commutative language CommutativeLanguage 2013-03-22 18:56:56 2013-03-22 18:56:56 CWoo (3771) CWoo (3771) 5 CWoo (3771) Definition msc 68Q70 commutative commutative closure