Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


The relation is

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

I am confused how this is derived. Any pointers?

share|cite|improve this question
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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.