I'm new here and im struggling right now on the following task:

I have to show that:

(L1 ∩ L2) o L3 = L1 o L3 ∩ L2 o L3

L1, L2 and L3 are three languages over the alphabet Σ. o stands for the concatenation of two languages.

kind regards


1 Answer 1


That claim is false (in general). Consider for example $\Sigma = \{a,b\}$, $L_1 = \{a\}$, $L_2 = \{ab\}$ and $L_3 = \{\varepsilon, b\}$.

Then, $(L_1 \cap L_2) = \emptyset$ and hence $(L_1 \cap L_2) \circ L_3 = \emptyset$. However $ab$ belongs to both $L_1 \circ L_3$ (since $a \in L_1$ and $b \in L_3$) and $L_2 \circ L_3$ (since $ab \in L_2$ and $\varepsilon \in L_3$), showing that $(L_1 \circ L_3) \cap (L_2 \circ L_3) \neq \emptyset$.


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