Search code examples
regexregular-language

what is equivalent 0* |a* |b* |(a|b)*

I've been trying this exercise, but i donk know how to keep going. What is equivalent to:

 0* |a* |b* |(a|b)*

Beeing 0 the void language, i know that 0* = ε, so the regular expression is now : 

ε | a* |b* |(a|b)*

I know that b* is contained in (a|b)* , as well is a*, because:

(a|b)* = (a*|b*)* = (a* b*)*

But its not the same, so at this point i dont know how to simplify this regular expression

Solution

  • Well, if both a* and b* are contained in (a|b)*, you can just remove a* and b* from your regex (because it's connected with an OR). Then you are left with ε|(a|b)*. Asterix means any number of repetitions, so if you select 0 repetitions of (a|b)*, you get ε. Therefore, your regex is equivalent to just:

    (a|b)*