Search code examples
regexsimplification

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

Solution

  • 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)*.