commutative language
Let be an alphabet and a word over . Write as a product of symbols in :
where . A of is a word of the form
where is a permutation on . The set of all permutations of is denoted by . If , it is easy to see that has
elements, where , the number of occurrences of in .
Define a binary relation on by: if is a permutation of . Then is a congruence relation on with respect to concatenation. In fact, is a commutative monoid.
A language over is said to be commutative if for every , we have . Two equivalent characterization of a commutative language are:
-
•
If , then .
-
•
, where is the Parikh mapping over (under some ordering).
The first equivalence comes from the fact that if is just a permutation of , and that every permutation on may be expressed as a product of transpositions. The second equivalence is the realization of the fact that is just the set
We have just seen some examples of commutative closed langauges, such as for any word , and , for any language .
Given a language , the smallest commutative language containing is called the commutative closure of . It is not hard to see that is the commutative closure of .
For example, if , then .
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 |
---|---|
Canonical name | CommutativeLanguage |
Date of creation | 2013-03-22 18:56:56 |
Last modified on | 2013-03-22 18:56:56 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 5 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 68Q70 |
Defines | commutative |
Defines | commutative closure |