[Solved]: Finding simpler equivalent regular expressions

ignougroup
Problem Detail: I’m doing an exercise from my book that says:

Let $r$ and $s$ be arbitrary regular expressions over the alphabet $Sigma$. Find a simpler equivalent regular expression: a. $r(r^*r + r^*) + r^*$ b. $(r + Lambda)^*$ c. $(r + s)^*rs(r + s)^* + s^*r^*$

The book doesn’t cover how to simplify regular expressions, so I searched online and I presumed you would use the algebraic laws for regular expressions. I was able to use these laws to come up with something for part a. only: a. $r(r^*r + r^*) + r^*$ $r(r^+ + r^*)+r^*$ $r(r^+ + r^+ + Lambda) + r^*$ $r(r^++Lambda)+r^*$ $rr^+ + rLambda + r^*$ $rr^+ + r + r^*$ I don’t know how to approach b. or c., because b. has $(r + Lambda)^*$ and c. has $(r+s)^*$, and I couldn’t find how to deal with these. Any hints?

Asked By : badjr

Answered By : Yuval Filmus

A better approach would be to understand what words do these regular expressions represent. For example, what words are in $(r+Lambda)^*$? They look something like $r_1r_2 Lambda r_3 Lambda = r_1r_2r_3$, where $r_1,r_2,r_3$ are generated by $r$. It seems that $Lambda$ isn’t making much of a difference. This should help you simplify $(r+Lambda)^*$. The same approach works for the other expressions (including the first one, which you haven’t simplified completely).
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10077