# How do I solve these questions regarding homomorphism?

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?
• 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$. – siracusa Oct 19 '19 at 4:32

## 1 Answer

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.