CODEWITHSUNDEEP
regex
Sossenbinder
Sossenbinder

Reputation: 5282

I need some help shortening this regular expression

I currently try to get into regular expressions for school and have to work on the task to shorten this regular expression:

r = 0(e + 0 + 1)* + (e + 1)(1 + 0)* + e

with e being the empty word epsilon.

So far I got to this:

r = 0(0 + 1)* + 1(1 + 0)* + e

considering the rule 

r* = (e + r)*

However, I don't really know how to continue. If it wasn't for the kleene star operators, I could use the distributive law, but that won't apply here. I can't really figure out a suitable law to continue on with this regex.

Any helpful tips?

Edit:

I think I got one step further by forming r to

r = 0(1 + 0)* + 1(1 + 0)* + e

and then being able to combine it to

r = (0 + 1)(0 + 1)* + e

Is that correct?

Also, we could then say

r = (0+1)*

which should be the final form

Upvotes: 4

Views: 181

Answers (1)

SamWhan
SamWhan

Reputation: 8332

I'd say that your own deduction is correct except for one thing. Taking your original

r = 0(e + 0 + 1)* + (e + 1)(1 + 0)* + e

removing e which according to you is empty, leaves

r = 0(0 + 1)* + 1(1 + 0)*

or in plain words 0 followed by any number of 0 or 1 or 1 followed by any number of 1 or 0. So the left side states that there has to be at least a 0 and the right side that there has to be a 1. That means that there must be at least a 0 or a 1. Now, your flavor of regex is one I've never seen so I don't know how to express one or more in your flavor (it's normally a +) so I'll express it in regular regex, which would be

r = [01]+

which simply means at least one0 or 1 repeated any number of times.

Regards.

Upvotes: 1

Related Questions