Proof for Kleene star and concatenation I'm currently learning Formal Languages and Automata theory.
I came across a question that I can't seem to solve. I need to prove that for Languages $L_1$ and $L_2$ over the alphabet $\Sigma$:
$$
(L_1L_2)^*L_1=L_1(L_2L_1)^*
$$
I tried proving it with double inclusion and say that $w\in (L_1L_2)^*=>w=xy_1,xy_2...xy_n$ but I have no idea how to even continue this proof.
I also thought of going in the direction that $(L_1L_2)^∗=L_1^*L_2^*$ but I'm not sure if this is true and how to proceed with it.
Will appreciate any help. Thanks!
 A: Recall that $\Sigma^*$ is a monoid under the catenation operation and that for any $L \subseteq \Sigma^*$, $L^*$ is the submonoid of $\Sigma^*$ generated by $L$. The fact that a set $S \subseteq \Sigma^*$ is a submonoid means that it is closed under catenation and contains the empty string $\epsilon$. The fact that $L^*$ is the submonoid generated by $L$ means that it is the smallest submonoid containing $L$.
If $L_1, L_2$ are any languages, I claim that
$$M =\{x \in \Sigma^* \mid \forall y \in L_1 . xy \in L_1 (L_2 L_1)^*\}$$
is a submonoid.
For consider that given $x_1, x_2 \in M$ and $y \in L_1$. Then we see that $x_2 y \in L_1 (L_2 L_1)^*$. Then write $x_2 y = a b$ where $a \in L_1$, $b \in (L_2L_1)^*$. Then $x_1 a \in L_1 (L_2 L_1)^*$, so write $x_1 a = c d$ where $c \in L_1$ and $d \in (L_2 L_1)^*$. Then we have $(x_1 x_2) y = x_1 (x_2 y) = x_1 (ab) = (x_1 a) b = (cd)b = c(db)$. Now $c \in L_1$, and since $d, b \in (L_2 L_1)^*$ and $(L_2 L_1)^*$ is a submonoid, $db \in (L_2 L_1)^*$. Thus, $c(db) \in L_1 (L_2 L_1)^*$. So $m$ is closed under catenation.
Furthermore, we see that for all $y \in L_1$, we have $\epsilon y = y \epsilon$. Since $\epsilon \in (L_2 L_1)^*$, we have $y \epsilon \in L_1 (L_2 L_1)^*$. Therefore, $\epsilon \in M$.
We have confirmed that $M$ is a submonoid of $\Sigma^*$. Now, we verify that $L_1 L_2 \subseteq M$. For suppose we have $x \in L_1 L_2$. Write $x = ab$ where $a \in L_1$, $b = L_2$. Then given $y \in L_1$, we have $xy = (ab) y = a (by)$. Since $a \in L_1$ and $(by) \in L_2 L_1 \subseteq (L_2 L_1)^*$, we have $a (by) \in L_1 (L_2 L_1)^*\}$. Thus, $x \in M$. So $L_1 L_2 \subseteq M$.
Now since $(L_1 L_2)^*$ is the smallest submonoid of $\Sigma^*$ containing $L_1 L_2$, and since $L_1 L_2 \subseteq M$ and $M$ is a submonoid of $\Sigma^*$, we see that $(L_1 L_2)^* \subseteq M$. Therefore, for all $x \in (L_1 L_2)^*$, for all $y \in L_1$, $xy \in L_1 (L_2 L_1)^*$. That is, $(L_1 L_2)^* L_1 \subseteq L_1 (L_2 L_1)^*$.
I leave the other direction as an exercise.
By the way, it's definitely not true that $L_1^* L_2^* = (L_1 L_2)^*$ in general. Just take $\Sigma = \{1, 2\}$ and $L_i = \{i\}$ to see this.
