Show that the regular expressions (a+b)* and (a*b*)* are equal.

2.5k Views Asked by At

Let $L_1 = L((a+b)^*)$ and $L_2 = L((a^*b^*)^*)$. I need to show that $w \in L_1 \Rightarrow w \in L_2$. I have already done the $\supseteq$ direction.

Here's what I did:

Suppose $w \in L_1$. If $w = \lambda$, then $w \in L_2$. Otherwise, $w \neq \lambda$, so $\exists k$ s.t.

$w = u_1u_2...u_k$ where $u_i = a$ or $u_i = b$. But since $a = a\lambda = ab^0$, and since $b = \lambda b = a^0b$, we have:

$u_i = ab^0$ or $u_i = a^0b$, $\forall i$. Hence $w \in L_2$.

Is there anything wrong with this? I have a feeling it is not complete, but I'm not sure.

1

There are 1 best solutions below

0
On BEST ANSWER

What you did is ok.

If you want you could also use "usual" regular expression inclusion as follow: $a^*=\epsilon+a^+$ hence $$ L_2=(a^*b^*)^* = (b^*+a^+b^*)^*$$ $b\subset b^*$ and $a\subset a^+$hence $$(b+ab^*)^*\subseteq L_2$$ and finally $\epsilon \subseteq b^*$ hence $$(b+a)^*\subseteq L_2$$