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?

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

Assume the notations used in the question is the ones as described in the Wikipedia entry on regular expression for formal language theory. More specifically, it is the variant where "+" is used for alternation. (If you want to interpret the question in the notation used in common programming languages, please check the first version of this answer. Also note this updated answer renders the some comments below outdated. Thanks to the commenters!)

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.