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) = {wmid h(x) = w}$ is only defined (nonempty) when $windelta^*$ 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
