0
$\begingroup$

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other.

The expression is:

$(A^*B^*)^* \subset (A^*B)^*A^*$

All I have so far is:

Let $x \in (A^*B^*)^*$ so $x$ takes on the form $x = a_1b_1...a_nb_n$ s.t. $n \in \mathbb{N}$ , $a_i \in A^*$ , $b_i \in B^*$

Now I need to find some $x$ in $(A^*B)^*A^*$ such that the $x$'s are the same. However, I can't get anything into a form similar to the one I have above. Any help would be greatly appreciated!

2 Answers 2

2

HINT: Start with some $ab$ with $a\in A^*$ and $b\in B^*$. If $b=\epsilon$, then $ab=a\in A^*B$. Otherwise, let $b=b_1\dots b_n$, where each $b_k\in B$. Then $ab=ab_1\epsilon b_2\epsilon\dots\epsilon b_n$; clearly $ab_1\in A^*B$, and $\epsilon b_k\in A^*B$ for $k=2,\dots,n$, so $ab\in (A^*B)^*$.

Can you finish it from here?

  • 0
    @alexthebake: Yes; another common notation for it is $\lambda$.2012-10-24
1

Hints:

1)For $a_{i}\in A$ we have that $a_{1}a_{2}....a_{n}=a_{1}\epsilon a_{2}\epsilon....\epsilon a_{n}$ note that $\epsilon\in B^{*}$.

2)For $b_{i}\in B$ we have that $b_{1}b_{2}...b_{m}=\epsilon b_{1}\epsilon b_{2}...\epsilon b_{m}$ note that $\epsilon\in A^{*}$.

  • 1
    @alexthebake - yes. this is the standart notation2012-10-24