Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am confused how this relation is derived for a language on alphabet V

A,B

The relation is

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

I am confused how this is derived. Any pointers?

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

You can proceed by showing that each is included in the other :

$A \cup B \subset A^*B^*$, because if $a \in A$, then $a = a.\varepsilon$ where $a \in A^*$ and $\varepsilon \in B^*$ (and similarly for $B$). Thus $(A \cup B)^* \subset (A^*B^*)^*$

Next, $A \subset A \cup B$ thus $A^* \subset (A \cup B)^*$ (and similarly with $B^*$), thus $A^*B^* \subset (A \cup B)^* (A \cup B)^* = (A \cup B)^*$, and finally $(A^* B^*)^* \subset ((A \cup B)^*)^* = (A \cup B)^*$

share|improve this answer
add comment

The answer given by mercio is good for a formal proof, but here's an answer in (mostly) English, just in case it's helpful:

Think about the definitions of the two sets $S := (A\cup B)^*$ and $T := (A^* B^*)^*$.

The set $S$ consists of all finite length strings whose symbols are in $A$ or $B$, while $T$ consists of all finite length strings which are a concatenation of alternating words from $A^*$ and $B^*$.
Any string in $T$ is a string of elements from $A\cup B$ and is hence in $S$. Conversely, any string in $S$ can be expressed as string in $T$, by 'lumping together' consecutive elements from the same set ($A$ or $B$) into a word in $A^*$ or $B^*$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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