0
$\begingroup$

Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?

$\endgroup$
2
$\begingroup$

Yes. Let $L_1=\{a\}, L_2=\{\epsilon\}$. Obviously both languages are regular and neither is a subset of the other. We then have $$ (L_1\cup L_2)^*=(a+\epsilon)^*=a^* $$ and since $$ L_1^*=a^*,\quad L_2^*=\epsilon^*=\epsilon $$ we have $$ L_1^*\cup L_2^*=a^*\cup \epsilon = a^* $$

$\endgroup$
  • 1
    $\begingroup$ More generally, any two regular languages where $L_2 \subseteq L_1^*$ and which aren't subsets of each other will do. $\endgroup$ – G. Bach Dec 1 '15 at 21:15

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.