[Solved]: Concatenation of the intersection of two languages

Problem Detail: 

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?

Asked By : DodoSerebro

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16334