Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

simplifying regular expression

I am going through exercises regarding regular expressions, and I am really unsure on how to do this.

The regular expression is:

((a*)(b*))* ∪ (a*)

I am really bad at this, but I think that ((a*)(b*))* can be simplified to (a ∪ b)* But if this is right, than the last ∪ (a*) is really just a repetition, so I figure the whole expression can be simplified to (a ∪ b)*. Does this seem correct?

Edit: ∪ stands for union

like image 636
user2795095 Avatar asked Nov 02 '22 00:11

user2795095


1 Answers

You are right. (a*b*)* can match any string of a's and b's, so can (a U b)*, therefore they are equivalent. (a U b)* intersect a* is a* so a* is a subset of (a U b)*. Consequently, the whole expression can be simplified to (a U b)*.

like image 82
perreal Avatar answered Nov 15 '22 13:11

perreal