Consider the following identities for regular expressions; some are false and so

Question

Consider the following identities for regular expressions; some are false and some are true. Decide which and in case it is false to provide the correct counterexample.

(a) R(S+T)=RS+RT

(b) (R*)*=R*

(c) (R*S*)*=(R+S)*

(d) (R+S)*=R*+S*

(e) S(RS+S)*R=RR*S(RR*S)*

(f) (RS+R)*R=R(SR+R)*

a) (d) is false and a counterexample is:

R={ab},T={a}, S={b}

b) (c) is false and a counterexample is:

R={ab},T={b}, S={b}

c) (e) is true

d) (e) is false and a counterexample is:

R={a,},T={b}, S={a,}

What is the answer? Explain please

Explanation / Answer

Option (d) should be corrent i.e. (e) is false and a counterexample is: R={a,},T={b}, S={a,}

Consider the following S(RS+S)*R=RR*S(RR*S)*

Let us convert this into a regular expression i.e b(ab+b)*a=aa*b(aa*b)*

In general our left hand side equation should always end with 'a' but our right side contains a string that is not ending with a i.e.

Hope you will understand this, for any further doubt do comment !

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.