Problem Detail: I’m enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings: $$(L_1cap L_2)cdot L_3 ≠ (L_1cdot L_3) cap (L_2cdot 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_1cap L_2)L_3subseteq L_1L_3cap 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_1cap 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
