3
$\begingroup$

Background: This is to be seen in the context of formal languages, very beginner-level.

My professor claims that concatenation is not distributive over intersection, meaning that $L \circ (L_1 \cap L_2) \neq (L \circ L_1) \cap (L \circ L_2)$ and $(L_1 \cap L_2) \circ L \neq (L_1 \circ L) \cap (L_2 \circ L)$.

While it seems silly of me to doubt what he says, I personally have trouble explaining this to myself and am looking for a counter example.

If I concatenate only with the intersection of $L_1, L_2$ it ought to be the same as concatenating first and then finding the duplicates, so to speak.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

When we say that concatenation doesn't distribute over intersection, we don't mean that $L(L_1\cap L_2) \neq LL_1 \cap LL_2$ for all languages $L,L_1,L_2$, but rather that this inequality holds for some $L,L_1,L_2$. Here is one example: $$ L = \{a,aa\}, L_1 = \{a\}, L_2 = \{aa\}. $$ In this case $L(L_1 \cap L_2) = \emptyset$ but $LL_1 \cap LL_2 = \{aaa\}$.

Improve this answer
$\endgroup$

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