enter image description here Questions:

  1. Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
  2. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and Γ, for languages A and B, respectively.

Questions to stack overflow:

  • How do I give the examples above? Do I make the state diagrams? Do I show it through the tuple-definition?
  • What are some examples of the questions above?
  • 2
    $\begingroup$ A homomorphism $f$ in this context maps from characters of $\Sigma$ to strings of $\Gamma^*$. So to define a specific $f$ you can just give a mapping for each character from $\Sigma$. $\endgroup$
    – siracusa
    Oct 19, 2019 at 4:32

1 Answer 1


Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$. First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$. The second is the map between words $$f':\Sigma^* \rightarrow \Gamma^*$$. The third is the map between languages $$f'':\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$.

The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$. And $f$ is usually easier to describe directly than $f''$.

Another important observation is that not all function of type $$\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.