homomorphism of languages

Let ${\mathrm{\Sigma }}_1$ and ${\mathrm{\Sigma }}_2$ be two alphabets. A function $h:{\mathrm{\Sigma }}_1^{*}\to {\mathrm{\Sigma }}_2^{*}$ is called a homomorphism if it is a semigroup homomorphism from semigroups ${\mathrm{\Sigma }}_1^{*}$ to ${\mathrm{\Sigma }}_2^{*}$. This means that

• $h$ preserves the empty word: $h(\lambda )=\lambda$, and

• $h$ preserves concatenation: $h(\alpha \beta )=h(\alpha )h(\beta )$ for any words $\alpha ,\beta \in {\mathrm{\Sigma }}_1^{*}$.

Since the alphabet ${\mathrm{\Sigma }}_1$ freely generates ${\mathrm{\Sigma }}_1^{*}$, $h$ is uniquely determined by its restriction to ${\mathrm{\Sigma }}_1$. Conversely, any function from ${\mathrm{\Sigma }}_1$ extends to a unique homomorphism from ${\mathrm{\Sigma }}_1^{*}$ to ${\mathrm{\Sigma }}_2^{*}$. In other words, it is enough to know what $h(a)$ is for each symbol $a$ in ${\mathrm{\Sigma }}_1$. Since every word $w$ over $\mathrm{\Sigma }$ is just a concatenation of symbols in $\mathrm{\Sigma }$, $h(w)$ can be computed using the second condition above. The first condition takes care of the case when $w$ is the empty word.

Suppose $h:{\mathrm{\Sigma }}_1^{*}\to {\mathrm{\Sigma }}_2^{*}$ is a homomorphism, $L_1\subseteq {\mathrm{\Sigma }}_1^{*}$ and $L_2\subseteq {\mathrm{\Sigma }}_2^{*}$. Define

$$h(L_1):=\{h(w)\mid w\in L\}\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}{h}^{-1}(L_2):=\{v\mid h(v)\in L_2\}.$$

If $L_1,L_2$ belong to a certain family of languages, one is often interested to know if $h(L_1)$ or $h^{-1}(L_2)$ belongs to that same family. We have the following result:

1. If $L_1$ and $L_2$ are regular, so are $h(L_1)$ and $h^{-1}(L_2)$.

2. If $L_1$ and $L_2$ are context-free, so are $h(L_1)$ and $h^{-1}(L_2)$.

3. If $L_1$ and $L_2$ are type-0, so are $h(L_1)$ and $h^{-1}(L_2)$.

However, the family $ℱ$ of context-sensitive languages is not closed under homomorphisms, nor inverse homomorphisms. Nevertheless, it can be shown that $ℱ$ is closed under a restricted class of homomorphisms, namely, $\lambda$-free homomorphisms. A homomorphism is said to be $\lambda$-free or non-erasing if $h(a)\ne \lambda$ for any $a\in {\mathrm{\Sigma }}_1$.

Remarks.

• Every homomorphism induces a substitution in a trivial way: if $h:{\mathrm{\Sigma }}_1^{*}\to {\mathrm{\Sigma }}_2^{*}$ is a homomorphism, then $h_s:{\mathrm{\Sigma }}_1\to P({\mathrm{\Sigma }}_2^{*})$ defined by $h_s(a)=\{h(a)\}$ is a substitution.

• One can likewise introduce the notion of antihomomorphism of languages. A map $g:{\mathrm{\Sigma }}_1^{*}\to {\mathrm{\Sigma }}_2^{*}$ is an antihomomorphism if $g(\alpha \beta )=g(\beta )g(\alpha )$, for any words $\alpha ,\beta$ over ${\mathrm{\Sigma }}_1$. It is easy to see that $g$ is an antihomomorphism iff $g\circ \mathrm{rev}$ is a homomorphism, where $\mathrm{rev}$ is the reversal operator. Closure under antihomomorphisms for a family of languages follows the closure under homomorphisms, provided that the family is closed under reversal.