Doubt 1:
What exactly Homomorphism of a language is?
DEFINITION:A homomorphism is a mapping h with domain Σ ∗ for some alphabet Σ which preserves concatenation:
h(v · w) =h(v) · h(w).
Simply speaking in homomorphism we replace each letter in a language with another letter in some other language.
Simple example:
String SHIVA can be converted to corresponding to ASCII language by replacing each letter with corresponding ASCII value as 8372728665.
Doubt 2:
What is the need of it?
It helps to translate one language to other easily by keeping all its properties same.
Doubt 3:
how is it closed under regular languages?
Proof:
Let E be a regular expression for L.
apply h to each symbol in E.
Language of resulting RE is h(L).
Example:
Let h(0) = ab; h(1) = c.
- Let L be the language of regular expression 01* + 10*.
- Then h(L) is the language of regular expression abc* + c(ab)*.
- Obviously h(L) is a regular language
