Proving Formal Languages are a subset of each other

Question

I am having difficulty proving these three languages are a subset from each other. I don't know where to begin with the proof, I have tried simplifying the operators to their definition but it ended up just extending the problem.

Let $L_1, L_2, L_3 ⊆ Σ^∗$. Prove that

1. $L_1 · (L_2 ∪ L_3) ⊇ L_1 · L_2 ∪ L_1 · L_3$
2. $L_1 · (L_2 ∩ L_3) ⊆ L_1 · L_2 ∩ L_1 · L_3$

Answer 1

1. Consider $w \in L_1 \cdot L_2 \cup L_1 \cdot L_3$. If $w$ is in the union of two sets, then $w$ has to be contained in at least one of the parts of the union, so $w \in L_1 \cdot L_2$ or $w \in L_1 \cdot L_3$.

   1a. Case $w \in L_1 \cdot L_2$: If $w$ is in the concatenation of two sets, $w$ can be partitioned into a word from the first set and a word from the second set, so $w = u \cdot v$ for some $u \in L_1$ and $v \in L_2$. If $v$ is in $L_2$, then $v$ is also in the union of $L_2$ and some other set, so $v \in L_2 \cup L_3$. If $u \in L_1$ and $v \in L_2 \cup L_3$, then $u \cdot v$ is in the concatenation of $L_1$ and $L_2 \cup L_3$. Therefore $w = u \cdot v \in L_1 \cdot (L_2 \cup L_3)$.

   1b. Case $w \in L_1 \cdot L_3$: Analogous to the first case with $L_3$ and $L_2$ exchanged.

2. Consider $w \in L_1 \cdot (L_2 \cap L_3)$. If $w$ is in the concatenation of $L_1$ and $L_2 \cap L_3$, then $w$ can be partitioned into a word from $L_1$ and a word from $L_2 \cap L_3$. Therefore $w = u \cdot v$ for some $u \in L_1$ and some $v \in L_2 \cap L_3$. If $v$ is in the intersection of two sets, it has to be contained in each of them, so $v \in L_2$ and $v \in L_3$. If $u \in L_1$ and $v \in L_2$, then their concatenation is in $L_1 \cdot L_2$, so $u \cdot v \in L_1 \cdot L_2$. If $u \in L_1$ and $v \in L_3$, then their concatenation is in $L_1 \cdot L_3$, so $u \cdot v \in L_1 \cdot L_3$. From $u \cdot v \in L_1 \cdot L_2$ and $u \cdot v \in L_1 \cdot L_3$, you can conclude that $w = u \cdot v \in L_1 \cdot L_2 \cap L_1 \cdot L_3$.

Answer 2

Both formulas follow from a single simple result:

if $L_1 \subseteq L_2$, then $LL_1 \subseteq LL_2$.

Proof. If $w \in LL_1$, then $w = uu_1$ for some $u \in L$ and $u_1 \in L_1$. Since $L_1 \subseteq L_2$, one also has $u_1 \in L_2$ and hence $w \in LL_2$.

Let us now come back to your questions.

1. Since $L_2 \subseteq L_2 \cup L_3$, one gets $L_1L_2 \subseteq L_1(L_2 \cup L_3)$. Similarly, $L_3 \subseteq L_2 \cup L_3$, whence $L_1L_3 \subseteq L_1(L_2 \cup L_3)$. It follows that $L_1L_2 \cup L_1L_3 \subseteq L_1(L_2 \cup L_3)$.
2. Since $L_2 \cap L_3 \subseteq L_2$, one gets $L_1(L_2 \cap L_3) \subseteq L_1L_2$. Similarly, $L_2 \cap L_3 \subseteq L_3$, whence $L_1(L_2 \cap L_3) \subseteq L_1L_3$. Therefore $L_1(L_2 \cap L_3) \subseteq L_1L_2 \cap L_1L_3$.

A final remark. Actually, the equality $L_1(L_2 \cup L_3) = L_1L_2 \cup L_1L_3$ holds (exercise), but in general $L_1(L_2 \cap L_3) \not= L_1L_2 \cap L_1L_3$ (other exercise).