\documentclass{article}
\begin{document}


\noindent
Which of the following statements holds for every three languages
$L_1$, $L_2$, $L_3$.

\medskip
\noindent
i) $(L_1 \cap L_2) L_3 = L_1 L_3 \cap L_2 L_3$ \\
FALSE. \\
Proof by counterexample: \\
$L_1 = \{a\}$ \\
$L_2 = \{b\}$ \\
$L_3 = \{c\}$ \\
$(L_1 \cap L_2) L_3 = \{\}\{c\} = \{c\}$ \\
$(L_1 L_3 \cap L_2 L_3) = \{ac\} \cap \{bc\} = \{\}$ \\
$\{c\} \ne \{\}$

\medskip
\noindent
ii) $(L_1^* = L_1^* L_1^*$ \\
TRUE. \\
To prove this claim, we must prove a: $(L_1^* \subseteq L_1^* L_1^*$ and b: $(L_1^* L_1^* \subseteq L_1^*$. \\
a) Take any $x \in L_1^*$ and show $x \in L_1^* L_1^*$. Observe $x = x \epsilon$. $x \in L_1^*$ by assumption and $\epsilon \in L_1^*$ by definition of $L_1^*$ therefore $x \in L_1^* L_1^*$. \\
b) Take any $x \in L_1^* L_1^*$ and show $x \in L_1^*$. Observe $x \in L_1^* L_1^*$ means $x = y z$ where $y \in L_1^*$ and $z \in L_1^*$. By definition of $L_1^*$ this means that $y \in L_1^n$ and $z \in L_1^m$ for some non-negative integers $n$ and $m$. This means that $y z \in L_1^\{n+m\}$, which in turn means that $x = y z \in L_1^*$ because by definition $L_1^\{n+m\} \in L_1^*$.

\medskip
\noindent
iii) $(L_1 \cup L_2) \cap L_3 = L_1 \cup (L_2 \cap L_3)$
FALSE. \\
Proof by counterexample: \\
$L_1 = \{a\}$ \\
$L_2 = \{b\}$ \\
$L_3 = \{c\}$ \\
$(L_1 \cup L_2) \cap L_3 = \{a,b\} \cap \{c\} = \{\}$ \\
$L_1 \cup (L_2 \cap L_3) = \{a\} \cup \{\} = \{a\}$ \\
$\{\} \ne \{a\}$

\end{document}
