homomorphism of languages
Let and be two alphabets. A function is called a homomorphism if it is a semigroup homomorphism from semigroups to . This means that
-
•
preserves the empty word: , and
-
•
preserves concatenation: for any words .
Since the alphabet freely generates , is uniquely determined by its restriction to . Conversely, any function from extends to a unique homomorphism from to . In other words, it is enough to know what is for each symbol in . Since every word over is just a concatenation of symbols in , can be computed using the second condition above. The first condition takes care of the case when is the empty word.
Suppose is a homomorphism, and . Define
If belong to a certain family of languages, one is often interested to know if or belongs to that same family. We have the following result:
-
1.
If and are regular, so are and .
-
2.
If and are context-free, so are and .
-
3.
If and are type-0, so are and .
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, -free homomorphisms. A homomorphism is said to be -free or non-erasing if for any .
Remarks.
-
•
Every homomorphism induces a substitution in a trivial way: if is a homomorphism, then defined by is a substitution.
-
•
One can likewise introduce the notion of antihomomorphism of languages. A map is an antihomomorphism if , for any words over . It is easy to see that is an antihomomorphism iff is a homomorphism, where 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 |