2
$\begingroup$

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?

2 Answers 2

1

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)^*$

1

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