6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is L.L3 the same as L1.L3 please? in the 2nd sentence $\endgroup$ – DodoSombrero Oct 24 '13 at 15:36
  • $\begingroup$ @DodoSerebro See my update, this was an abuse of notation from my part. $\endgroup$ – Gilles 'SO- stop being evil' Oct 24 '13 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.