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 contextfree, so are $h({L}_{1})$ and ${h}^{1}({L}_{2})$.

3.
If ${L}_{1}$ and ${L}_{2}$ are type0, so are $h({L}_{1})$ and ${h}^{1}({L}_{2})$.
However, the family $\mathcal{F}$ of contextsensitive languages is not closed under^{} homomorphisms, nor inverse^{} homomorphisms. Nevertheless, it can be shown that $\mathcal{F}$ is closed under a restricted class of homomorphisms, namely, $\lambda $free homomorphisms. A homomorphism is said to be $\lambda $free or nonerasing 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.
References
 1 S. Ginsburg, The Mathematical Theory of ContextFree Languages, McGrawHill, New York (1966).
 2 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey (1981).
Title  homomorphism of languages 

Canonical name  HomomorphismOfLanguages 
Date of creation  20130322 18:55:06 
Last modified on  20130322 18:55:06 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Synonym  $\u03f5$free 
Synonym  nonerasing 
Related topic  StringSubstitution 
Related topic  Substitution 
Defines  homomorphism 
Defines  antihomomorphism 
Defines  $\lambda $free 