You are here
Homecommutative language
Primary tabs
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 permutation 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\midv_{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\midw_{a}=w_{b}=w_{c}\}$.
Remark. The above example illustrates the fact that the families of regular languages and contextfree languages are not closed under commutative closures. However, it can be shown that the families of contextsensitive languages and type0 languages are closed under commutative closures.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Mathematics Subject Classification
68Q70 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections