Is $(L_1L_2)^* \subset L_1^*L_2^*$?

83 Views Asked by At

Is $(L_1L_2)^* \subset L_1^*L_2^*$ ?

I tried with simple languages,
$L_1 = \{0\}$
$L_1^* = \{\epsilon, 0, 00, 000, \ldots\}$

$L_2 = \{ab, ba\}$
$L_2^* = \{\epsilon, ab, ba, abab, baba, abba, baab, \ldots\}$

$L_1L_2 = \{0ab, 0ba\}$
$(L_1L_2)^* = \{\epsilon, 0ab, 0ba, 0ab0ab, 0ba0ba, \ldots\}$
$L_1^*L_2^* = \{\epsilon, 0ab, 0ba, 00ab, 000baab, \ldots\}$

So then $(L_1L_2)^* \subset L_1^*L_2^*$, because it doesn't contain strings that begin with more than one $0$.

What about $L_1^* \cap L_2^*$ and $(L_1 \cap L_2)^*$?
I arrived to the answer that $(L_1 \cap L_2)^* \subset L_1^* \cap L_2^*$


Edit: I see where I went wrong for the first pair, and I understand that my example doesn't show that the $LHS$ is a subset of the $RHS$. Is there any language $L_1$ that is a subset of another language $L_2$, other than $L_1 = L_2$?

1

There are 1 best solutions below

2
On BEST ANSWER

$(L_1 L_2)^* \nsubseteq L_1^* L_2^*$ in general. Take $L_1 = \{a\}, \ L_2 = \{b\}$. The $LHS$ contains strings that look like $ababab...ab$, while the $RHS$ only contains strings of the form $aaaaabbbbb$.