Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings: $$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$
I've tried a lot of sets for e.g. $L1 = \{a,b,c,d\}$, $L2 = \{a,f,g\}$, $L3 = \{s,d,h\}$. but always the LHS comes out equal to the RHS instead of unequal. Any idea how to prove this?
First, you may notice that there is a one-sided containment here. It always holds that $(L_1\cap L_2)L_3\subseteq L_1L_3\cap L_2L_3$ (prove it!)
From this, you see that in order for the equality to fail, you need to get a strict containment. Intuitively, this means that you need the concatenation with $L_3$ to add words to both $L_1$ and $L_2$.
One way to achieve this is, for example, to first let $L_1\cap L_2=\emptyset$, and then "tailor" $L_3$ to fix this emptiness.
A concrete example is below (hidden as spoiler, hover mouse to see it):
$L_1=\{a\}$, $L_2=\{aa\}$, $L_3=\{a,\epsilon\}$.
If all the words in $L_3$ have the same length $n$, then you can unambiguously decompose a word $w \in \mathscr{A}^* \cdot L_3$ (where $\mathscr{A}$ is the alphabet) into $u \in L$ and $v \in L_3$ such that $uv = w$: take the last $n$ letters of $w$, call that $v$, and let $u$ be $w$ without its last $n$ letters. Therefore, under this condition, a word is in $(L_1\cap L_2)\cdot L_3$ iff its last $n$ letters are in $L_3$ and the corresponding prefix is in both $L_1$ and $L_2$, which is equivalent to the word being in $(L_1\cdot L_3) \cap (L_2\cdot L_3)$.
The same goes if all the words in $L_1 \cup L_2$ have the same length.
So to find a counterexample, you need to find a case where the words of the concatenation can potentially be decomposed in an ambiguous way. In particular, $L_3$ needs to contain at least two words of different lengths, as does $L_1 \cup L_2$.
Take $L_3 = \{\epsilon, a\}$, which is the simplest example of a language with words of different lengths. And let's take $L_1 = \{\epsilon\}$ and $L_2 = \{a\}$, again the simplest way of having words of different lengths in $L_1 \cup L_2$. Then $$ \begin{align} (L_1\cap L_2)\cdot L_3 &= \varnothing \cdot L_3 = \varnothing \\ (L_1\cdot L_3) \cap (L_2\cdot L_3) &= \{\epsilon,a\} \cap \{a,aa\} = \{a\} \\ \end{align} $$ There are two ways to decompose $a$ in $(L_1\cdot L_3) \cap (L_2\cdot L_3)$: one that makes it an element of $L_1 \cdot L_3$ and one that makes it an element of $L_2 \cdot L_3$. Thus the word is in the intersection of the concatenations even though it is not in the concatenation of the intersections (which is empty).
