3
$\begingroup$

I want to prove that $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ is not always true.

If $L_1 = (ab)^*$ and $L_2 = (ba)^*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L_1 \cap L_2) = 2$ while $H(L_1) \cap H(L_2) = (11)^*$.

Is the above example correct to prove the above statement? Is it allowed to map two symbols to one same symbol?

$\endgroup$
  • $\begingroup$ A homomorphism always satisfies $H(\epsilon) = \epsilon$. Other than that, the proof works. I explained in detail what a homomorphism is in my answer. $\endgroup$ – Yuval Filmus Jan 19 '18 at 12:38
3
$\begingroup$

Given two finite non-empty alphabets $\Sigma,\Delta$, a homomorphism is a mapping $h\colon \Sigma^* \to \Delta^*$ that satisfies the following two properties:

  • $h(\epsilon) = \epsilon$.
  • $h(xy) = h(x) h(y)$.

(Actually the first property follows from the second, since it implies that $h(\epsilon) = h(\epsilon \epsilon) = h(\epsilon) h(\epsilon)$, and so $h(\epsilon) = \epsilon$.)

It is not hard to show that $h$ is determined by its value on letters of $\Sigma$. Indeed, if $w = \sigma_1\ldots \sigma_n$, where $\sigma_1,\ldots,\sigma_n \in \Sigma$, then $h(w) = h(\sigma_1) \ldots h(\sigma_n)$. Conversely, if $h_0\colon \Sigma \to \Delta^*$, then the mapping $h(\sigma_1 \ldots \sigma_n) = h_0(\sigma_1) \ldots h_0(\sigma_n)$ defines a homomorphism. In formal language theory, one often identifies $h$ and $h_0$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So the mapping need not be one to one right ? $\endgroup$ – Rajesh R Jan 19 '18 at 13:14
  • 1
    $\begingroup$ I gave a complete definition. Any mapping that satisfies this definition is a homomorphism. $\endgroup$ – Yuval Filmus Jan 19 '18 at 13:15
  • 1
    $\begingroup$ Ok, after applying the definition, it seems that homomorphism need not be one to one. But this answer says it has to be one to one cs.stackexchange.com/questions/43779/… $\endgroup$ – Rajesh R Jan 19 '18 at 13:22
  • 1
    $\begingroup$ Hendrik meant that $h(w)$ is single-valued, whereas $h^{-1}(w)$ is many-valued, i.e., a set of words rather than a single word. $\endgroup$ – Yuval Filmus Jan 19 '18 at 13:26
  • 1
    $\begingroup$ Ohh. I thought that he meant the function or mapping has to be injective. $\endgroup$ – Rajesh R Jan 19 '18 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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