# Finding simpler equivalent regular expressions

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^+ + r\Lambda + 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?

• $(r + \Lambda)^* = r^*$, as you can check (or think what they mean!). And $(r + s)^* = (r^* s^*)^*$ is sometimes handy. Feb 25 '13 at 4:33
• Apparently, this is a hard problem, algorithmically.
– Raphael
Feb 25 '13 at 7:30

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).