linear erasing
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.
Definition. Let be a language over an alphabet , a homomorphism over , and a non-negative integer. is said to be a -linear erasing on if for any word , we have
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:
Theorem 1.
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 .
References
- 1 A. Salomaa, Formal Languages
, Academic Press, New York (1973).
- 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation
to Automata, Addison-Wesley, (1969).