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 $\lambda$ -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 $L$ be a language over an alphabet $\Sigma$ , $h$ a homomorphism over $\Sigma$ , and $k$ a non-negative integer. $h$ is said to be a $k$ -linear erasing on $L$ if for any word $u\in L$ , we have $$|u|\le k |h(u)|,$$ where $|u|$ stands for the length of $u$ .

It is clear that if $h$ is a $k$ -linear erasing on $L$ , then it is a $m$ -linear erasing for any $m\ge k$ . Also, if $h$ is a $0$ -linear erasing on $L$ , then $L$ is either $\lbrace \lambda\rbrace$ , or the empty set $\varnothing$ . In addition, if $h$ is a $k$ -linear erasing on $L$ , and $L'\subseteq L$ , then it is a $k$ -linear erasing on $L'$ . Consequently, any $\lambda$ -free homomorphism is a $k$ -linear erasing on any $L$ over $\Sigma$ , for any $k\ge 1$ .

However, the notion of linear erasing is language dependent. For example, let $\Sigma = \lbrace a,b,c\rbrace$ . Let $L_1 = \lbrace a^nb^n \mid n\ge 0\rbrace$ and $L_2= \lbrace a^nc^n \mid n\ge 0\rbrace$ . Suppose $h$ is the homomorphism on $\Sigma^*$ with $h(a)=\lambda$ , $h(b)=b^2$ and $h(c)=c$ . Then $h$ is a $1$ -linear erasing on $L_1$ , and a $2$ -linear erasing on $L_2$ .

Definition Let be a family of languages over $\Sigma$ . Then is said to be closed under linear erasing if for any , and any homomorphism $h$ which is a $k$ -linear erasing on $L$ for some $k\ge 0$ , then .

Clearly, if is closed under homomorphism, it is closed under linear erasing, and thus the families of regular, 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 $s$ over $\Sigma$ a $k$ -linear erasing on a language $L$ if $|u|\le k|v|$ for any $v\in s(u)$ . If $L$ is context-sensitive such that $s(u)$ is context-sensitive for each $u\in L$ , then $s(L)$ is context-sensitive provided that $s$ is a $k$ -linear erasing on $L$ .

Bibliography

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).