## You are here

Homelinear erasing

## Primary tabs

# linear erasing

It is well-known that, among all of the language families in the Chomsky hierarchy, the family $\mathscr{S}$ of context-sensitive languages is the only one that is not closed under arbitrary homomorphisms. Nevertheless, $\mathscr{S}$ 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 $\mathscr{S}$ 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|\leq 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\geq k$. Also, if $h$ is a $0$-linear erasing on $L$, then $L$ is either $\{\lambda\}$, or the empty set $\varnothing$. In addition, if $h$ is a $k$-linear erasing on $L$, and $L^{{\prime}}\subseteq L$, then it is a $k$-linear erasing on $L^{{\prime}}$. Consequently, any $\lambda$-free homomorphism is a $k$-linear erasing on any $L$ over $\Sigma$, for any $k\geq 1$.

However, the notion of linear erasing is language dependent. For example, let $\Sigma=\{a,b,c\}$. Let $L_{1}=\{a^{n}b^{n}\mid n\geq 0\}$ and $L_{2}=\{a^{n}c^{n}\mid n\geq 0\}$. 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 $\mathscr{L}$ be a family of languages over $\Sigma$. Then $\mathscr{L}$ is said to be *closed under linear erasing* if for any $L\in\mathscr{L}$, and any homomorphism $h$ which is a $k$-linear erasing on $L$ for some $k\geq 0$, then $h(L)\in\mathscr{L}$.

Clearly, if $\mathscr{L}$ 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 $\mathscr{S}$ 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|\leq 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$.

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

## Mathematics Subject Classification

68Q70*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections