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^*
$$
Best Answer
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^*$$