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$
1
  • $\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$ Commented Jan 19, 2018 at 12:38

1 Answer 1

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$.

$\endgroup$
6
  • 1
    $\begingroup$ So the mapping need not be one to one right ? $\endgroup$
    – Ramesh
    Commented Jan 19, 2018 at 13:14
  • 1
    $\begingroup$ I gave a complete definition. Any mapping that satisfies this definition is a homomorphism. $\endgroup$ Commented Jan 19, 2018 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$
    – Ramesh
    Commented Jan 19, 2018 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$ Commented Jan 19, 2018 at 13:26
  • 1
    $\begingroup$ Ohh. I thought that he meant the function or mapping has to be injective. $\endgroup$
    – Ramesh
    Commented Jan 19, 2018 at 13:29

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.