Show that, for any languages $L_1$ and $L_2$, we have (1). $L_1L_1^* = L_1^*L_1L_1^*$

Question

I am very confused on how to solve this problem. I know $L$ star is $0$ or more times, but proving it I do not know what to do

Answer 1

The thing to do is consider a word $w$.

What does it say about $w$ if $w\in L_1L_1^*$? What about $w\in L_1^*L_1L_1^*$? Compare and try to convince yourself whether they are equivalent.

Answer 2

Since your question is now on MathStackExchange, here is a mathematical approach to your question. I will drop the index $1$ for simplicity. The result immediately follows from two simpler formulas:

1. $LL^* = L^*L$
2. $L^*L^* = L^*$

To prove (1), just write $$ LL^* = L\Bigl(\sum_{n \geqslant 0} L^n\Bigr) = \sum_{n \geqslant 0}L^{n + 1} = \Bigl(\sum_{n \geqslant 0} L^n\Bigr)L = L^*L. $$ For (2), you could do the same type of computation using series, but it is simpler to prove separately that $L^*L^* \subseteq L^*$ (can you see why?) and that $ L^* = L^*1 \subseteq L^*L^* $.

Notation. Let $A$ be the alphabet. Then ${\cal P}(A^*)$, the set of languages is a semiring under union as addition and the usual product of languages as multiplication. For this reason, I denote union additively, the empty language as $0$ (since for all $L$, $0 + L = L = L +0$) and the language reduced to the empty word as $1$ (since for all $L$, $1L = L = L1$).