You are here
Homehomomorphism of languages
Primary tabs
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:
However, the family $\mathscr{F}$ of contextsensitive 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 nonerasing 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 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).
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