What is inverse homomorphism?

Inverse homomorphism is a closure property of regular languages. It allows us to map the input and output elements of a homomorphic language back to the original language.

We can say that if $L$ is a regular language, its inverse homomorphism $H^{-1}$ is as follows:

Note: The inverse homomorphism of a regular language is also regular.

Example

Let's suppose there is a language $L$ that has inputs in the set $\Sigma \{ a,b,c \}$, and we have mapped it with $\Gamma \{ 0,1\}$ homomorphically.

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

If we take $L=\{0011001\}$, then:

We see that the inverse homomorphism of such a language may have many translations/instances.

Note: The homomorphism of an inverse homomorphism of a language is a subset of the original language $H(H^{-1}(L)) ⊆ L$.

Closure under homomorphism

Now, let's see the proof of how inverse homomorphism is closed under regular languages. Let $L$ be the language of a DFA $A$.

Using $A$ and its homomorphic image $H$ , we construct a DFA for $H^{-1}(L)$ that has the same states as $A$. However, before choosing the next state, it interprets the input symbols according to $H$.

The transition function for such a DFA is as follows:

Here, we determine $B$'s transitions by applying the homomorphic image $H$ to the input symbols.

Using induction on$|w|$ , we show that:

$B$ accepts $w$ if, and only if, $A$ accepts $H(w)$. This is because $A$ and $B$ have the same accepting states. Simply, $B$ only accepts strings ($w$) present in $h^{-1} (L)$.