there is a letter such that no word in begins with and contains more than consecutive occurrences of in it,
for any ,
Here, is the set of all letters in that occur in words of .
It is easy to see that any -restricted homomorphism on is a -linear erasing on , for if is a non-empty word, then we may write , where each , and each is a non-empty word not containing any occurrences of . Then
Note that since for each . A -linear erasing is in general not a -restricted homomorphism, an example of which is the following: and given by and . Then is a -linear erasing, but not a -restricted homomorphism, on .
A family of languages is said to be closed under restricted homomorphism if for every , and every -restricted homomorphism on , . 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.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 18:59:11|
|Last modified on||2013-03-22 18:59:11|
|Last modified by||CWoo (3771)|