It is well-known that, among all of the language families in the Chomsky hierarchy, the family of context-sensitive languages is the only one that is not closed under arbitrary homomorphisms. Nevertheless, is shown to be closed under a more restricted class of homomorphisms, namely the -free homomorphisms. Question: can we enlarge this class of homomorphisms so that is still closed under the larger class? The answer is yes.
where stands for the length of .
It is clear that if is a -linear erasing on , then it is a -linear erasing for any . Also, if is a -linear erasing on , then is either , or the empty set . In addition, if is a -linear erasing on , and , then it is a -linear erasing on . Consequently, any -free homomorphism is a -linear erasing on any over , for any .
However, the notion of linear erasing is language dependent. For example, let . Let and . Suppose is the homomorphism on with , and . Then is a -linear erasing on , and a -linear erasing on .
Definition Let be a family of languages over . Then is said to be closed under linear erasing if for any , and any homomorphism which is a -linear erasing on for some , then .
Clearly, if is closed under homomorphism, it is closed under linear erasing, and thus the families of regular (http://planetmath.org/RegularLanguage), context-free, and type-0 languages are all closed under linear erasing. We also have the following:
The family of context-sensitive languages is closed under linear erasing.
Remark. The theorem above can be generalized. Call a substitution over a -linear erasing on a language if for any . If is context-sensitive such that is context-sensitive for each , then is context-sensitive provided that is a -linear erasing on .
|Date of creation||2013-03-22 18:58:54|
|Last modified on||2013-03-22 18:58:54|
|Last modified by||CWoo (3771)|