Homomorphism

Homomorphism is a closure property of regular languages that allows the mapping of input and output elements of a language to another language without changing its properties.

We can say, if $L$ is a regular language, then its homomorphism $H$ is:

Note: The homomorphism of a regular language is also regular

Example

Let's discuss an example below:

Suppose there is a language $L$ that has inputs in the set $\Sigma \ \{ a,b \}$. We'll map the elements of this language with $\Gamma \{ 0,1 \}$.

First, the homomorphic images of each input symbol/alphabet are determined. In this case, we may take:

Take $L=\{ aa,bab\}$ then:

The language above is the homomorphism of the language $L$.

Closure under homomorphism

Now we'll see the proof of how homomorphism is closed under regular languages. The algorithm is:

• Let $E$ be a regular expression of a certain language.

• Map each symbol/alphabet with its homomorphic image.

• The resulting RE will be $H(L)$ which must be regular.

Suppose:

Let a regular expression of a regular language $L$ be $001+0^*$.

Then $H(L)$ is the language of $acacbc + ac^*$.

By equating, we see that $H(L)$ is also a regular language.