linear erasing

It is well-known that, among all of the languagePlanetmathPlanetmath families in the Chomsky hierarchy, the family 𝒮 of context-sensitive languages is the only one that is not closed underPlanetmathPlanetmath arbitrary homomorphismsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. 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 L be a language over an alphabet Σ, h a homomorphism over Σ, and k a non-negative integer. h is said to be a k-linear erasing on L if for any word uL, we have


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 mk. Also, if h is a 0-linear erasing on L, then L is either {λ}, or the empty setMathworldPlanetmath . In addition, if h is a k-linear erasing on L, and LL, then it is a k-linear erasing on L. Consequently, any λ-free homomorphism is a k-linear erasing on any L over Σ, for any k1.

However, the notion of linear erasing is language dependent. For example, let Σ={a,b,c}. Let L1={anbnn0} and L2={ancnn0}. Suppose h is the homomorphism on Σ* with h(a)=λ, h(b)=b2 and h(c)=c. Then h is a 1-linear erasing on L1, and a 2-linear erasing on L2.

Definition Let be a family of languages over Σ. Then is said to be closed under linear erasing if for any L, and any homomorphism h which is a k-linear erasing on L for some k0, then h(L).

Clearly, if is closed under homomorphism, it is closed under linear erasing, and thus the families of regularPlanetmathPlanetmath (, context-free, and type-0 languages are all closed under linear erasing. We also have the following:

Theorem 1.

The family S of context-sensitive languages is closed under linear erasing.

Remark. The theorem above can be generalized. Call a substitution s over Σ a k-linear erasing on a language L if |u|k|v| for any vs(u). If L is context-sensitive such that s(u) is context-sensitive for each uL, then s(L) is context-sensitive provided that s is a k-linear erasing on L.


  • 1 A. Salomaa, Formal LanguagesMathworldPlanetmath, Academic Press, New York (1973).
  • 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their RelationMathworldPlanetmathPlanetmath to Automata, Addison-Wesley, (1969).
Title linear erasing
Canonical name LinearErasing
Date of creation 2013-03-22 18:58:54
Last modified on 2013-03-22 18:58:54
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 68Q70
Synonym limited erasing
Related topic RestrictedHomomorphism