#regularexpressions #Theoryofcomputation

Question

L = (a+b)$\small ^*$b is equivalent to ____________?

A. (ab$\small^*$)$\small^+$

B. (a$\small^+$b$\small^*$)$\small^+$

C. b$\small^*$(ab$\small^*$)$\small^*$b

D. None

Answer 1

Answer : C

This are some common Expression

(a+b)* = (b+a)* = b*(ab*)* =a *(ba*)* = (a*+b*)* = (a+b*)* = (a*+b)* = (a*b*)* = (b*a*)*

So

(a+b)*b = b*(ab*)*b

 

 

Comments

can you explain how (a+b)*=b*(ab*)* ??

---

@a_believer

(a+b)* = ε, a, b, aa, bb, ab, ba, aaa…, bbb…, aba… bab…  

                     $-$ Set of all strings over the alphabet a, b

b*(ab*)* = ε, 

[ε.a*.ε = a* = ε, a, aa, aaa...],

[b*.ε = b* = ε, b, bb, bbb...],

[ε.(ab*)* = ε, a, ab, abb, abbb….],

[b*.ab* = b*a.ε = b*a = a, ba, bba, bbba, bbb….a, and  b*ab* = a, ba, ab, bab, bbab, babb, bbb….abbb...]

[b*(ab*)* = b*(ab, abab, ababab…...) = bab, bababa…..]

           $-$ This regular expression also covering all the possibilities of strings over the alphabets a, b

So (a+b)* = b*(ab*)*