# homomorphism of languages

Let $\Sigma_{1}$ and $\Sigma_{2}$ be two alphabets. A function $h:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ is called a homomorphism if it is a semigroup homomorphism from semigroups $\Sigma_{1}^{*}$ to $\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\Sigma_{1}^{*}$.

Since the alphabet $\Sigma_{1}$ freely generates $\Sigma_{1}^{*}$, $h$ is uniquely determined by its restriction to $\Sigma_{1}$. Conversely, any function from $\Sigma_{1}$ extends to a unique homomorphism from $\Sigma_{1}^{*}$ to $\Sigma_{2}^{*}$. In other words, it is enough to know what $h(a)$ is for each symbol $a$ in $\Sigma_{1}$. Since every word $w$ over $\Sigma$ is just a concatenation of symbols in $\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:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ is a homomorphism, $L_{1}\subseteq\Sigma_{1}^{*}$ and $L_{2}\subseteq\Sigma_{2}^{*}$. Define

 $h(L_{1}):=\{h(w)\mid w\in L\}\qquad\mbox{and}\qquad 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. 1.

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

2. 2.

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

3. 3.

If $L_{1}$ and $L_{2}$ are type-0, so are $h(L_{1})$ and $h^{-1}(L_{2})$.

However, the family $\mathscr{F}$ of context-sensitive languages is not closed under homomorphisms, nor inverse homomorphisms. Nevertheless, it can be shown that $\mathscr{F}$ 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)\neq\lambda$ for any $a\in\Sigma_{1}$.

Remarks.

• Every homomorphism induces a substitution in a trivial way: if $h:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ is a homomorphism, then $h_{s}:\Sigma_{1}\to P(\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:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ is an antihomomorphism if $g(\alpha\beta)=g(\beta)g(\alpha)$, for any words $\alpha,\beta$ over $\Sigma_{1}$. It is easy to see that $g$ is an antihomomorphism iff $g\circ\operatorname{rev}$ is a homomorphism, where $\operatorname{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.

## References

• 1 S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
• 2 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
Title homomorphism of languages HomomorphismOfLanguages 2013-03-22 18:55:06 2013-03-22 18:55:06 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 68Q45 $\epsilon$-free non-erasing StringSubstitution Substitution homomorphism antihomomorphism $\lambda$-free