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)* ?

  • $\begingroup$ Counter-example to both: sr $\endgroup$ – Pseudonym May 7 '18 at 5:40
  • $\begingroup$ @Pseudonym could you please elaborate? $\endgroup$ – centrinok May 7 '18 at 5:42
  • $\begingroup$ 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. $\endgroup$ – Evil May 7 '18 at 6:02
  • $\begingroup$ Try $r=a$ and $s=b$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.