2
$\begingroup$

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

$\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$

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 $.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.