<p>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^*$.</p>

<p>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!</p>

CC BY-SA 2.5
2010-11-16T05:29:58.017Z
2010-11-16T05:29:58.017Z
Mark Reitblatt
<p>I'm currently taking a subject on theoretical computer science. This is not a homework question.</p>

<p>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?</p>

<p>$A^* \cup B^* = (A \cup B)^*$
</p>

<p>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.</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-11-16T05:18:42.403Z
I just looked at the FAQ and I realise this question isn't exactly research-level. Should it be deleted?
oadams
CC BY-SA 2.5
2010-11-16T05:25:37.727Z
Yeah, it should probably be deleted. Thanks for self-policing.
Mark Reitblatt
CC BY-SA 2.5
2010-11-16T05:26:56.743Z
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 :-)
Marcos Villagra
<fl.formal-languages>
Languages and their operations: determining equivalence
oadams
# Languages and their operations: determining equivalence

(Asked by: username_0 on 2010-11-16)

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.

Thanks.

**Tags:** fl.formal-languages
> **Comments:**
> **username_0**: I just looked at the FAQ and I realise this question isn't exactly research-level. Should it be deleted?  
> **username_1**: Yeah, it should probably be deleted. Thanks for self-policing.  
> **username_2**: 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 :-)  

---

## 1 answers

### Answer by username_1 on 2010-11-16. Score: 5 | Accepted answer

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!


---

