linear erasing
It is well-known that, among all of the language^{} families in the Chomsky hierarchy, the family $\mathcal{S}$ of context-sensitive languages is the only one that is not closed under^{} arbitrary homomorphisms^{}. Nevertheless, $\mathcal{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 $\mathcal{S}$ is still closed under the larger class? The answer is yes.
Definition. Let $L$ be a language over an alphabet $\mathrm{\Sigma}$, $h$ a homomorphism over $\mathrm{\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 $\{\lambda \}$, or the empty set^{} $\mathrm{\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 $\mathrm{\Sigma}$, for any $k\ge 1$.
However, the notion of linear erasing is language dependent. For example, let $\mathrm{\Sigma}=\{a,b,c\}$. Let ${L}_{1}=\{{a}^{n}{b}^{n}\mid n\ge 0\}$ and ${L}_{2}=\{{a}^{n}{c}^{n}\mid n\ge 0\}$. Suppose $h$ is the homomorphism on ${\mathrm{\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 $\mathcal{L}$ be a family of languages over $\mathrm{\Sigma}$. Then $\mathcal{L}$ is said to be closed under linear erasing if for any $L\in \mathcal{L}$, and any homomorphism $h$ which is a $k$-linear erasing on $L$ for some $k\ge 0$, then $h(L)\in \mathcal{L}$.
Clearly, if $\mathcal{L}$ 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 $\mathrm{S}$ of context-sensitive languages is closed under linear erasing.
Remark. The theorem above can be generalized. Call a substitution $s$ over $\mathrm{\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$.
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).
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 |