[Solved]: Is an inverse homomorphism always a homomorphism?

Problem Detail: 

Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

EDIT: The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.

Asked By : Kyselejsyreček

Answered By : Hendrik Jan

If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \{w\mid h(x) = w\}$ is only defined (nonempty) when $w\in\delta^*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse is a substitution, mapping the letter $\delta$ to the set $\Sigma$ and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one, an inverse homomorphism in many cases is one-to-many. (If the inverse morphism is one-to-at-most-one [injective] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43779