Geek Answers Handbook

Simplify this regex

I am doing some pre-exam exercises for my compiler class and should simplify this regex.

(a U b)*(a U e)b* U (a U b)*(b U e)a*

Obviously, e is an empty string, and U means concatenation.

Until now, I think that one of (a U b) * can be deleted as a union U a = a. However, I cannot find any other simplifications, and I am not doing very well with other problems so far :(

Any help is appreciated, thanks a lot!

+7
source share
4 answers

A little rusty in regular expression, but if * still represents "zero or more trenches," you can replace:

 (a U e)b* for (a U b)*

which leaves the first part with:

 (a U b)*(a U b)* = (a U b)*

On the right side you have

 (b U e)a* = (b U a)*

Now, since U b = b U a, you get:

 (a U b)*(a U b)*

on the right side, which leaves only

 (a U b)* U (a U b)* = (a U b)*

I think that it's...

+1
source

First translate into English language description:

 (a U b)*(a U e)b* U (a U b)*(b U e)a*

Translated to:

Any sequence a or b s followed by optional a , followed by any number b s.

OR

Any number a and b s followed by optional b , followed by any number a s

There are many overlaps here - at least (a U b)*(a U e) exactly matches (a U b)* , because "Any sequence a and b s" necessarily ends with a or epsilon (since any string can end with epsilon) so that these groups can be eliminated leaving

 (a U b)*b* U (a U b)*a*

Translated to:

Any sequence a or b s followed by any number b s.

OR

Any number a and b s followed by any number a s

Now the first section of these external groups is the same, so it allows you to collapse them into one

 (a U b)*(a* U b*)

Translated to:

Any sequence a or b s followed by any number a OR by any number b s.

now hold the minute, “Any sequence from A and B” necessarily ends with “Any sequence a OR any sequence b s”, which means that everything that matches the first part can match the entire regular expression (because the second part can have a length of zero ), so why don't we just do it

 (a U b)*

Ta Da. Plain.

+3
source

I think all this is equivalent to (a U b)* (or in most regular expressions, (a|b)* )

+1
source

I will give you an idea of ​​how I will resolve it: (not very formal and without guarantee)

Look at the left side of the main U:

(a U b) * - What does this mean? The combination of a's and b's of length n, where n> = 0.

Next comes (a U e). What do we have here? A or an empty word. If we wanted this, we could just get it in the previous part. If we want e, we can still leave it. Please note that we do not need to take a, because we have the opportunity to choose e. Therefore, we can skip this whole part.

What's next? b *. What is it? Like many used, as we want. We could get them in the first part! we can leave it!

So, the only thing on the left is (a U b) *.

Lets look at the right side:

Well, now it’s easy, we can use the same idea that these are just different letters.

We also get (a U b) * in the same way.

So, in the end we have (a U b) * U (a U b) *, which, as you know, is equal to (a U b) *.

0
source

More articles:


All Articles