patternMinor
Finding simpler equivalent regular expressions
Viewed 0 times
equivalentregularexpressionssimplerfinding
Problem
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?
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?
Solution
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).
Context
StackExchange Computer Science Q#10077, answer score: 7
Revisions (0)
No revisions yet.