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

  • $\begingroup$ If L1 just accepts "a", and L2 just accepts "aa", I believe that's a counterexample $\endgroup$ Commented Feb 17, 2016 at 16:11
  • 1
    $\begingroup$ No, $\subseteq$ relation is satisfied for your counter example. $\endgroup$ Commented Feb 17, 2016 at 16:28
  • $\begingroup$ Ah, yes, missed that. $\endgroup$ Commented Feb 17, 2016 at 16:29

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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