What is the simplest regular expression that generates the same language as (a|b)*b*(a|b)+b+

• A: (a|b)+b+
• B: b*(a|b)+b+
• C: (a|b)*(a|b)+b+
• D: (a|b)+
• E: (a|b)+b

Answer:   E

We can do this in steps as:

1. (a|b)*b*(a|b)+b+
2. (a|b)*(a|b)+b+     (a|b)* can absorb b*
3. (a|b)+b+     (a|b)+ can absorb (a|b)*
4. (a|b)+b*b     b+ = b*b
5. (a|b)+b     (a|b)+ can absorb b*