Which of the following regular expressions are equivalent?

Question

1. $(a^*+b^*)^*$
2. $(a^*b^*)^*$
3. $(a+b)^*$
4. $(a+b^*)^*$
5. $(a^*+b)^*$
6. $(b^*a+a^*b)^*$
7. $(a+ab)^*$
8. $(ba+ab)^*$

Comments

Answer is already well explained by Pragy

1-6 are wired combination of (a+b)*  

7th cannot produce following strings  : (b,bb,bbb,....,ba,bba,baba,.....)
8th cannot produce following strings : (a,b,aa,bb,aba,bab,...........)

Answer 1

1. $(a^*+b^*)^*$
       $\equiv (a+a^*+b+b^*)^*$
       $\equiv (a+b)^*$
    
2. $(a^*b^*)^*$
       $\equiv \biggl ( (\epsilon+a^*)(\epsilon+b^*) \biggr )^*$
       $\equiv \biggl ( \epsilon + a^* + a^*b^* + b^* \biggr )^*$
       $\equiv (a+b)^*$
    
3. $(a+b)^*$
    
4. $(a+b^*)^* $
       $\equiv \biggl (a+(b+b^*) \biggr )^*$
       $\equiv (a+b)^*$
    
5. $(a^*+b)^* $
       $\equiv \biggl ((a+a^*)+b \biggr )^*$
       $\equiv (a+b)^* $
       Note: Symmetric to 4
    
6. $(b^*a+a^*b)^*$
       $\equiv \biggl ((a+b^*a) + (b+a^*b) \biggr )^*$
       $\equiv (a+b)^*$
    
7. $(a+ab)^*$
       Not equivalent to any other of these eight RegEx-es.
    
8. $(ba+ab)^*$
       Not equivalent to any other of these eight RegEx-es. Not even to 7!

Comments

in 1st part, how are you getiing (a + a^* + b + b^* )^*  = ( a + b)^* , either intuitively or there is some formula?

---

Not everything in the world is a formula.

If

• you already have a RegEx which can generate a string of any length $(\ldots)^*$, and
• you have a choice of all the letters in the alphabet for every character in the string $(a+b+a^*+b^*)$

Then, you can generate any string (which can be generated with the alphabet).

With that $a$ and $b$ alone you can generate any string. Having an additional choice of $a^*$ and $b^*$ won't make your language any bigger, since your language already has everything!

---

thank you. Yeah exactly, i am getting this by intuition. I was just curious about to know if any formula exists for the above statement.