# Trying to simplify a particular regular expression

The question is as follows

$$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$

But I am unable to solve this regex expression. My answer is as follows:

\begin{alignat*}{2} (a^* + (ba)^* )^* ( b+\epsilon)\qquad &\text{(using property} (a^* b^*)^* = (a^*+b^*)^* = (a+b)^*\text{)}\\ =(a+ ba)^* ( b+\epsilon)\qquad &\text{(using the above again)} \end{alignat*}

This is my final answer but it is not as stated on the right side of the proof. So can you tell where am I doing wrong? Is my proof correct?

• One reason you're having problems is that the two expressions denote different things. Try getting bbb from the left expression. – Rick Decker Sep 28 '18 at 13:17
• What do you mean by "solve" here? – Raphael Sep 28 '18 at 15:29

Suppose the task is to determine whether the following equality of regular expressions is correct, $$(a^* (ba)^* )^* (b\text{+}\epsilon) = (a\text{+}b)^* (b\text{+}\epsilon)$$ then the answer is NO.
Why? Let us consider word $$bb$$. The right side is, in fact, the set of all words over the alphabet $$\{a,b\}$$. In particular, the right side contains $$bb$$. Can the left side contains $$bb$$? If the first $$b$$ in $$bb$$ comes from the part $$(b\text{+}\epsilon)$$, then it must be the end of the word, but there is another $$b$$ following the first $$b$$. If the first $$b$$ comes from the part $$(ba)$$, then it must be followed by an $$a$$, which is not the case. Since the right side contains $$bb$$ but the left side does not, the equality cannot hold.
Now suppose the task is to simplify the left side of that incorrect equality, $$(a^* (ba)^* )^* (b\text{+}\epsilon)$$ then a likely answer is, as given and proved by OP correctly, $$(a\text{+}ba)^*(b+\epsilon)$$ The equality of these two regular expressions can also be understood easily by observing that the language is the set of all words over the alphabet $$\{a,b\}$$ that have no two consecutive $$b$$'s.