homomorphism of languages
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:
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 .
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.
- 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|
|Date of creation||2013-03-22 18:55:06|
|Last modified on||2013-03-22 18:55:06|
|Last modified by||CWoo (3771)|