patternMinor
Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms
Viewed 0 times
l_1homomorphismscapforl_2refuting
Problem
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?
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?
Solution
Given two finite non-empty alphabets $\Sigma,\Delta$, a homomorphism is a mapping $h\colon \Sigma^ \to \Delta^$ that satisfies the following two properties:
(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$.
- $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$.
Context
StackExchange Computer Science Q#86960, answer score: 3
Revisions (0)
No revisions yet.