homomorphism of languages


Let Σ1 and Σ2 be two alphabets. A function h:Σ1*Σ2* is called a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath if it is a semigroup homomorphism from semigroups Σ1* to Σ2*. This means that

  • h preserves the empty wordPlanetmathPlanetmathPlanetmath: h(λ)=λ, and

  • h preserves concatenationMathworldPlanetmath: h(αβ)=h(α)h(β) for any words α,βΣ1*.

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

h(L1):={h(w)wL}  and  h-1(L2):={vh(v)L2}.

If L1,L2 belong to a certain family of languagesPlanetmathPlanetmath, one is often interested to know if h(L1) or h-1(L2) belongs to that same family. We have the following result:

  1. 1.

    If L1 and L2 are regularPlanetmathPlanetmath, so are h(L1) and h-1(L2).

  2. 2.

    If L1 and L2 are context-free, so are h(L1) and h-1(L2).

  3. 3.

    If L1 and L2 are type-0, so are h(L1) and h-1(L2).

However, the family of context-sensitive languages is not closed underPlanetmathPlanetmath homomorphisms, nor inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath homomorphisms. Nevertheless, it can be shown that is closed under a restricted class of homomorphisms, namely, λ-free homomorphisms. A homomorphism is said to be λ-free or non-erasing if h(a)λ for any aΣ1.

Remarks.

  • Every homomorphism induces a substitution in a trivial way: if h:Σ1*Σ2* is a homomorphism, then hs:Σ1P(Σ2*) defined by hs(a)={h(a)} is a substitution.

  • One can likewise introduce the notion of antihomomorphism of languages. A map g:Σ1*Σ2* is an antihomomorphism if g(αβ)=g(β)g(α), for any words α,β over Σ1. It is easy to see that g is an antihomomorphism iff grev is a homomorphism, where 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
Canonical name HomomorphismOfLanguages
Date of creation 2013-03-22 18:55:06
Last modified on 2013-03-22 18:55:06
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 68Q45
Synonym ϵ-free
Synonym non-erasing
Related topic StringSubstitution
Related topic Substitution
Defines homomorphism
Defines antihomomorphism
Defines λ-free