toc

Question

Consider a regular expression over the alphabet set $\{r,s\}$. The following regular expressions are to be considered

1. $( r^{*}s^{*})^{*}+ (r^{+}s^{+})^{*}$
2. $(r^{+}s^{+}r^{+} )^{+}+ (\varepsilon + r)^{*}$
3. $(rs^{*}+sr^{*})^{*}+(\varepsilon +s)$
4. $( (rs^{*})^{*}r)^{*}+( (sr^{*})^{*}r)^{*}$

Choose the correct answer?

• A. all are equivalent to $(r+s)^{*}$
• B. all are equivalent to $(r+s)^{+}$
• C. all denote an infinite number of strings but not equivalent to $(r+s)^{*}$
• D. all denotes a finite number of strings

Comments

a) cannot be option beoz from 2) we can not generate no of s's..
b) same as above also here null is not there rest contain null..
d) all donate finite no of string since a) option has (a+b)* so this option also false.. so we left with c option ???

---

Yeah, C should be the answer.

---

Given answer is A?

Answer 1

Please correct me if I am wrong.

 

In option (1) $(r^{*}s^{*})^{*} + (r^{+}s^{+})^{*}$ , so we can generate $((r^{*}s^{*})(r^{*}s^{*}).....(r^{*}s^{*}) ) + ((r^{+}s^{+})(r^{+}s^{+})............(r^{+}s^{+}))$.

So , if we put r as null , we would be able to get s , if we put s as null ., we will able to get all r.

Also , we can get any combination of s and r.