# Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪ (rs)*.

I think this is not true. And I believe this would always be true :

(r ∪ s)* = r* ∪ s*

I wanted to clarify this because of (rs)*. What do you think the right hand side would be if r* ∪ s* ∪ (rs)* ?

• Counter-example to both: sr – Pseudonym May 7 '18 at 5:40
• @Pseudonym could you please elaborate? – centrinok May 7 '18 at 5:42
• r and s are regular expressions, try to generate sr with your proposal (It is neither from r* ∪ s* ∪ (rs)*). Try rss or srs as well. – Evil May 7 '18 at 6:02
• Try $r=a$ and $s=b$. – Yuval Filmus May 7 '18 at 7:20

Consider the alphabet $\Sigma = \{a,b\}$, and the regular expressions $r = a$ and $s = b$. Then $(r+s)^* = \Sigma^*$ whereas $a^*+b^*$ and $a^*+b^*+(ab)^*$ are both smaller.