HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding simpler equivalent regular expressions

Submitted by: @import:stackexchange-cs··
0
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?

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.