## You are here

Homerestricted homomorphism

## Primary tabs

# restricted homomorphism

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)$,

$h(a)=\left\{\begin{array}[]{ll}\lambda&\textrm{if }a=b\\ a&\textrm{otherwise.}\end{array}\right.$

Here, $\operatorname{Alpha}(L)$ is the set of all letters in $\Sigma$ that occur in words of $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}\leq 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}\leq|h(u)|+n(k-1)\leq|h(u)|+(% k-1)|h(u)|=k|h(u)|.$ |

Note that $n\leq|h(u)|$ since $1\leq|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=\{a,ab\}^{*}$ and $h:\{a,b\}\to\{a,b\}$ 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 $\mathscr{F}$ of languages is said to be *closed under restricted homomorphism* if for every $L\in\mathscr{F}$, and every $k$-restricted homomorphism $h$ on $L$, $h(L)\in\mathscr{F}$. By the previous paragraph, we see that if $\mathscr{F}$ is closed under linear erasing, it is closed under restricted homomorphism. The converse of this is not necessarily true.

# References

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

## Mathematics Subject Classification

68Q45*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