Regular Expression - Equality

Question

I want to know whether the following Regular Expressions are Equal ?
(a+b) *
   =  (a* + b*)*
   =  (a* + b)*
   =  (a + b*)*
   =  (a*  b*)*
   =  (b*  a*)*
   =  a*(ba*)*
    = (a*b)*a*

Comments

all are correct !

---

Sir, Can u pls tell how (a+b) *  = a*(ba*)*
Im not able to understand this one

---

See $(a+b)^*$ means $\epsilon$ or any sequence of a's or b's

consider $a^*(ba^*)^*$ :

1.We can derive $\epsilon$

2.If we want to derive consecutive sequences of a then $a^*$ can be used keeping $(ba^*)^*$ as $\epsilon$

If we want to derive $b^*$ then $a^*$ can be kept $\epsilon$ and $(ba^*)^* = (ba^*)(ba^*)(ba^*)^*$ so we can keep $a^* as \epsilon$ and keeping choosing b every time, so we get $b^*$

3. Now to derive any sequence of a and b, again consider $a^*(ba^*)* = a^*(ba^*)(ba^*)(ba^*)^* = a^*(ba^*)^* (ba^*)(ba^*)$, using these we can derive any sequence of a and b.

---

Yup....  All expressions can derive all possible strings

Answer 1

• 1st four options : 

check if it is possible to get one a separately and one b separately inside bracket. if it is possible then given regex = $\Sigma ^*$

---

• Last two options :

---

$\begin{align*} &R= a^* \bf{\color{red}{\left ( ba^* \right )^*}} = a^*{\color{red}{R_1}} \\ &{\bf\color{red}{R_1}}= \left [ {\color{blue}{b,ba,baa,baaa,..... }}\right ]^{\large\bf\color{red}{*}} \\ &{\bf\color{red}{R_1}}= {\large \bf \epsilon} \;\; + b(a+b)^{\large\bf\color{red}{*}} \rightarrow (1) \\ \\ \hline \\ &\text{Now,} \\ &{\bf\color{red}{R_1}} = \bf{\color{red}{\left ( ba^* \right )^*}} = {\large \bf \color{red}{\epsilon}} \;\; + \bf{\color{red}{\left ( {\color{blue}{b}}a^* \right )}}.\bf{\color{red}{\left ( ba^* \right )^*}} \\ &\Rightarrow {\bf\color{red}{R_1}} ={\large \bf \color{red}{\epsilon}} \;\; + \bf\color{blue}{b}.\left [ \bf{\color{red}{a^*}}.\bf{\color{red}{\left ( ba^* \right )^*}} \right ] \rightarrow (2) \\ \\ &\text{Compare } (1) \text{ and } (2) \rightarrow (a+b)^* = \left [ \bf{\color{red}{a^*}}.\bf{\color{red}{\left ( ba^* \right )^*}} \right ] \\ \\ \hline \\ &\text{Now using } (pq)^*p = p(qp)^* \\ \end{align*} \\$

$\begin{align*} &(a+b)^* = \left [ \bf{\color{red}{a^*}}.\bf{\color{red}{\left ( ba^* \right )^*}} \right ] = \left [ .\bf{\color{red}{\left ( a^*b \right )^*}}.\bf{\color{red}{a^*}} \right ] \\ \end{align*} \\$

Comments

I am a 2017 gate aspirant like you . not a sir

---

R1=ϵ+b(a+b)*→(1) how id u write this iam not able to get u

---

R1=ϵ+b.[a∗.(ba∗)∗]→(2) and this also can u explain