Show a counter-example to disprove the following statement:
If $R1$ and $R2$ are two regular expressions, then $L((R1 \cup R2)^*) = L(R1^* \cup R2^*)$.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Try $R_1 = a$ and $R_2 = b$. $\endgroup$– Yuval FilmusFeb 9, 2018 at 11:31
-
1$\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question and making better use of this site in the future. When you're asking to find a counter-example, a good place to start would be to try some possibilities (and you could show us in the question kinds of things you've already tried). $\endgroup$– D.W. ♦Feb 10, 2018 at 4:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $\{a\} = R1$ and $\{b\} = R2$. $'aba'$ belongs to $L((R1 \cup R2)^*)$ but not to $L(R1^* \cup R2^*)$.
explentation:
$'aba'$ belongs to $L((R1 \cup R2)^*)$ since $a$ belongs to $R1$ than with using the $*$ itiration we take $b$ from $R2$ than again we take $a$ from $R1$ by using $*$
$'aba'$ does not belong to $L(R1^* \cup R2^*)$ excepts only $a^n$ or $b^m$.
this answer is based on @Yuval Filmus
