regular expression

Question

(r + s)* = r* + s*

why this expression is false?

Comments

if u have to generate "rs" string then how will u generate from right-hand part of ur expression???

---

because regular expression $(r+s)^{*}$ can generate any string with input symbol r and s.

but strings generated by the regular expression $r^{*}+s^{*}$ =$\left \{ \epsilon,r,rr,rr....,s,ss,sss... \right \}$

 

$(r+s)^{*}\equiv (r^{*}+s^{*})^{*}\equiv (r^{*}+s)^{*}\equiv (r+s^{*})^{*}\equiv (r^{*} s^{*})^{*}\equiv (s^{*}r^{*})^{*}$

All these are equivalent.

Answer 1

here value of * indicate the length of string...say *=2 now look at LHS (r+s)^2..

we can write it as (r+s)(r+s)...means from 1st bracket pick r or s and from 2nd one pick r or s ...say form first we have r and form 2nd one we have s .....and there is concatenation in them hence resultant string is "rs"..

coming to RHS we have r* + s* now put *=2 we get

(r)(r) + (s)(s) which is same as "rr+ss"....means no we we can have combination as "rs" or "sr"....only string of "r" or "s "...is possible hence they are not equivalent....

Comments

thank u