I'm currently taking a subject on theoretical computer science. This is not a homework question.

I'm having trouble figuring out to show the equivalence or disprove the equivalence. Consider any two languages $A$ and $B$. Is the following statement true or false?

$A^* \cup B^* = (A \cup B)^*$

Honestly, I use the above example mainly to ensure my question is less subjective. However I'm more concerned about the generalised approach to determining whether languages are equivalent (or subsets of each other and such) when operated on by various operators (kleene star, union, intersection, difference, concatenation). If I know that they are not equivalent I can basically just start bruteforcing for counter-examples, however I can't really think of any structured and consistent approach to answering questions such as the above.



closed as off topic by Mark Reitblatt, Kaveh, Marcos Villagra, Dave Clarke, Robin Kothari Nov 16 '10 at 14:39

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I just looked at the FAQ and I realise this question isn't exactly research-level. Should it be deleted? $\endgroup$ – oadams Nov 16 '10 at 5:18
  • 2
    $\begingroup$ Yeah, it should probably be deleted. Thanks for self-policing. $\endgroup$ – Mark Reitblatt Nov 16 '10 at 5:25
  • 1
    $\begingroup$ yes, this is not research related. Regarding your question, use the definition of * operator exactly like it is on both sides and you'll get the answer :-) $\endgroup$ – Marcos Villagra Nov 16 '10 at 5:26

Nope. Let $A = \{a\}$, $B= \{b\}$. Then $A^* = \{\epsilon,a,aa, \ldots\}$ and similarly for $B$. So, $A^*\cup B^*$ contains strings of repeated "a" or repeated "b". But $(A\cup B)^*$ contains strings like $ab$, which you can't get from $A^*$ or $B^*$.

I'd suggest looking at a book like Sipser for a good coverage of languages like these and how to prove properties like equivalence. In particular, he has a great number of exercises to work through. Good luck!


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