Let $h$ be a homomorphism over an alphabet $\Sigma$ . Let $L$ be a language over $\Sigma$ . We say that $h$ is $k$ -restricted on $L$ if

1. there is a letter $b\in \operatorname{Alpha}(L)$ such that no word in $L$ begins with $b$ and contains more than $k-1$ consecutive occurrences of $b$ in it,
2. for any $a\in \operatorname{Alpha}(L)$ ,
   

It is easy to see that any $k$ -restricted homomorphism on $L$ is a $k$ -linear erasing on $L$ , for if $u\in L$ is a non-empty word, then we may write $u=v_1 b^{m_1} v_2 b^{m_2} \cdots v_n b^{m_n}$ , where each $0<m_i\le k-1$ , and each $v_i$ is a non-empty word not containing any occurrences of $b$ . Then $$|u| = |v_1\cdots v_{n-1}| + \sum_{i=1}^n m_i \le |h(u)|+n(k-1) \le |h(u)|+(k-1)|h(u)| = k|h(u)|.$$ Note that $n\le |h(u)|$ since $1\le |v_i|$ for each $i=1,\ldots, n$ . A $k$ -linear erasing is in general not a $k$ -restricted homomorphism, an example of which is the following: $L=\lbrace a,ab\rbrace^*$ and $h:\lbrace a,b\rbrace \to \lbrace a,b\rbrace$ given by $h(a)=a^2$ and $h(b)=\lambda$ . Then $h$ is a $1$ -linear erasing, but not a $1$ -restricted homomorphism, on $L$ .

A family of languages is said to be closed under restricted homomorphism if for every , and every $k$ -restricted homomorphism $h$ on $L$ , . By the previous paragraph, we see that if is closed under linear erasing, it is closed under restricted homomorphism. The converse of this is not necessarily true.

Bibliography

1

A. Salomaa, Formal Languages, Academic Press, New York (1973).