I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*) $$ I think that it's true since this can be rewritten as $$ \bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$$ and in general, $$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$$ I may be wrong since it has been a long time since i have done anything with set theory, and this is taken as given. Thanks
2
$\begingroup$
$\endgroup$
-
$\begingroup$ If L1 just accepts "a", and L2 just accepts "aa", I believe that's a counterexample $\endgroup$ – Millie Smith Feb 17 '16 at 16:11
-
1$\begingroup$ No, $\subseteq$ relation is satisfied for your counter example. $\endgroup$ – Shreesh Feb 17 '16 at 16:28
-
$\begingroup$ Ah, yes, missed that. $\endgroup$ – Millie Smith Feb 17 '16 at 16:29
4
$\begingroup$
$\endgroup$
Yes, it is true. But the argument to support the conjecture is incorrect.
The correct proof is as follows: $L_1 \cap L_2 \subseteq L_1 $ and therefore $(L_1 \cap L_2)^* \subseteq L_1^*$. (argument: if $A \subseteq B$ then $A^* \subseteq B^*$). Similarly $(L_1 \cap L_2)^* \subseteq L_2^*$.
Therefore $(L_1 \cap L_2)^* \subseteq (L_1^* \cap L_2^*)$ (argument: if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$).
Anyway you can not write $(A \cap B)^i \cup (C \cap D)^j = (A^i \cup C^j) \cap (B^i \cup D^j)$.
Correct relation is: $(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup D) \cap (A \cup D) \cap (B \cup C) $
However $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$ is correct because
$\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_1^i $ and $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_2^i $.
