Prove or disprove that $(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$ where $L_i$ denotes a formal language

Question

Prove or disprove that $$(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$$ where $L_i$ denotes a formal language

Proof:

$$\begin{align} (L_1\cap L_2)L_3 &= \{xy \mid (x \in L_1 \land x\in L_2 ) \land y\in L_3\}\\ &= \{xy \mid (x\in L_1 \land y\in L_3 ) \land (x\in L_2 \land y\in L_3)\} \\ &= L_1L_3 \cap L_2L_3. \end{align}$$ $\square$

On the other hand there also exists a contradiction: Let $$L_1 = \{a\}, L_2 = \{ab\}, L_3 = \{b,bb\}$$ We get that $$ (L_1\cap L_2)L_3 = \emptyset$$ while $$L_1L_3\cap L_2L_3 = \{abb\},$$

which leads to the conclusion that my proof is wrong somehow, I've been sitting on why it's wrong for a while but I can't find where my mistake is...

Answer 1

$$\bigl\{xy \mid (x\in L_1 \land y\in L_3 ) \land (x\in L_2 \land y\in L_3)\big\} = L_1L_3 \cap L_2L_3$$

This equality is wrong, it should be a $\subset$ : in your example, $abb$ belongs to the second set and no to the first.

A correct equality is : $$L_1L_3 \cap L_2 L_3 = \bigl\{ z \mid (\exists x_1 \in L_1,y_1 \in L_3, x_1y_1 = z) \wedge (\exists x_2 \in L_2,y_2 \in L_3, x_2y_2 = z) \bigr\}$$ In the RHS, the $x_1$ and $x_2$ need not be equal, so we cannot conclude that they belong to $L_1\cap L_2$.

Answer 2

Just a complement to SolubleFish answer. A language $L$ is suffix when no word of $L$ is a proper suffix of another word of $L$. More formally, the conditions $ps \in L$ and $s\in L$ imply $p = 1$ (the empty word).

I claim that the equality $$ (*) \qquad(L_1\cap L_2)L = L_1L\cap L_2L $$ holds when $L$ is a suffix language. Indeed \begin{multline} L_1L \cap L_2L = \big\{z \mid \text{$z = x_1x$ for some $x_1 \in L_1, x \in L$}\\ \text{and $z = x_2x'$ for some $x_2 \in L_2, x' \in L$} \big\} \end{multline} Now, the equality $z = x_1x = x_2x'$ implies that either $x$ is a suffix of $x'$ or $x'$ is a suffix of $x$. But when $L$ is a suffix language, this implies $x = x'$, whence $x_1 = x_2$. It follows that $z \in (L_1 \cap L_2)L$ and thus $L_1L \cap L_2L \subseteq (L_1 \cap L_2)L$. Since $L_1 \cap L_2 \subseteq L_1$ and $L_1 \cap L_2 \subseteq L_2$, the opposite inclusion $(L_1 \cap L_2)L \subseteq L_1L \cap L_2L$ also holds, which proves $(*)$.

Note that in your counterexample, the language $L = \{b, bb\}$ is not a suffix language. Also note that if $L$ is a prefix language (the dual notion: no word of $L$ is a proper prefix of another word of $L$), then the equality $L(L_1 \cap L_2) = LL_1 \cap LL_2$ holds.