Can we say... Given L1 and L2.
Is the following true? $$ L_{1}^{*} \cap L_{2}^{*} = (L_{1}^{*} \cap L_{2}^{*})^{*} $$
I think it is true but I can't be sure. What permutation of either wouldn't be contained in each other. Sorry I don't know how to format on Math Exchange to make things look better.
-Steve
On
Let $L$ be a language of the free monoid $A^*$. The answer easily follows form the fact that $L = L^*$ if and only if $L$ is a submonoid of $A^*$.
Now $L_1^*$ and $L_2^*$ are submonoids of $A^*$ and hence their intersection is a submonoid of $A^*$. Thus $L_1^* \cap L_2^*$ is a submonoid of $A^*$ and it is equal to its own star.
Left to right is easy, because the set closure operator preserves all elements of the set. So now it's left to prove the right-to-left case. For this, assume an element $u$ in $(L_1* \cap L_2*)*$. It is of the form $u_1u_2\dots u_n$ with each $u_i \in L_1*$ and $u_i \in L_2*$. Now, consider the case of $u_i \in L_1*$. Since this is true for all $u_i$, and the sets are closed under concatenation, then $u = u_1u_2\dots u_n \in L_1*$. Same for $L_2*$. So it's in the intersection, and we're done.