Proof for equivalence of two regular expressions

Question

I have to show via equivalence transformation, that these two regular expressions are equivalent:

$$(ab+b^*a^*) = (a+b^*)(a^*+b)$$

Can someone give me a hint how to show this? I am only allowed to use these equivalences:

$$ R+S = S+R \\ (R+S)+T = R+(S+T) \\ (R S) T = R (S T) \\ \emptyset + R = R + \emptyset = R \\ \varepsilon R = R \varepsilon = R \\ \emptyset R = R \emptyset = \emptyset \\ R (S + T) = RS + RT \\ (S + T)R = SR + TR \\ R + R = R\\ (R^*)^* = R^* \\ (\varepsilon + R)^* = R^* \\ \emptyset^* = \varepsilon \\ \varepsilon^* = \varepsilon \\ (\varepsilon + R)R^* = R^*(\varepsilon + R) = R^*\\ RR^* = R^*R \\ R^* + R = R^* \\ \varepsilon + RR^* = R^* $$

My best attempt so far.

Answer 1

First, for any $R$,

$$R^*+\epsilon=\epsilon+(\epsilon+R)R^*=\epsilon+\epsilon R^*+RR^*=\epsilon+R^*+RR^*=R^*+(\epsilon+RR^*)=R^*+R^*=R^*$$

So

$$b^*a^*=(b^*+\epsilon)a^*=b^*a^*+\epsilon a^*=b^*a^*+a^*=b^*a^*+(\epsilon+a)a^*=b^*a^*+\epsilon a^*+aa^*=(b^*+\epsilon)a^*+aa^*=b^*a^*+aa^*$$

Likewise

$$b^*a^*=b^*(a^*+\epsilon)=b^*a^*+b^*\epsilon=b^*a^*+b^*=b^*a^*+(\epsilon+b)b^*=b^*a^*+\epsilon b^*+bb^*\\=b^*a^*+b^*\epsilon+b^*b=b^*(a^*+\epsilon)+b^*b=b^*a^*+b^*b$$

So that $b^*a^*=b^*a^*+aa^*+b^*b$.

Now

$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$

Answer 2

EDIT to clarify my answer. The core of the solution is highlighted in yellow.

I introduce the following useful concept, that permits to better reason about regular expressions.

Definition. I write $R\subset S$ if there exists $T$ such that $R+T=S$.

Lemma. If $R\subset S$, then $R+S=S$.

Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □

Now, back to your problem. We have $$ (a+b^*)(b+a^*) = ab + aa^* + b^*b + b^*a^* , $$ but $aa^*\subset b^*a^*$ and $b^*b\subset b^*a^*$, so $$ (a+b^*)(b+a^*) = ab + b^*a^* . $$

You may ask, why is $aa^*\subset b^*a^*?$ Well, that's easy 'cause $$ b^*a^* = (\epsilon+b^*)(\epsilon+a)a^* = aa^* + \text{other terms}. $$

---

For the nitpickers. In the last formula, we used also $b^*=b^*+\epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+\epsilon=RR^*+\epsilon+\epsilon = RR^*+\epsilon=R^*$.

Otherwise, using our useful subset concept, notice that $\epsilon\subset R^*$, because $R^*=\epsilon+RR^*$; but then our lemma says $R^*+\epsilon=R^*$.

---

To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.

Just compare my short formulas with those of the accepted answer.