Allen Career Institute:Regular Expression

Question

The regular expression 0*(10*)* denote the same set as

(1)	(1*0)*1*
(2)	0+(0+10)*
(3)	(0+1)*10(0+1)*
(4)	None of these

Isnot 1) as same as given expression? 

Comments

a*(b.a*)* == b*(a.b*)* == (a+b)*

Not getting any counter example for 1. I think it is also (a+b)*

@Deepakk Poonia (Dee) can you please help!!

---

$0^{*}(10^{*})^{*}$. -> RegEx Original

Let's check with each regEx.

1.$(1^{*}0)^{*}1^{*}$.

If we observe carefully , the string $1110$ is in RegEx Original,  but it is not possible in this regEx , thus both are not same.

2.$0+(0+10)^{*}$.

$0100$ is present in this regEx set , but this is not present in the original regEx set . Thus not same.

3.$(0+1)^{*}10(0+1)^{*}$.

This set does not contain $\epsilon$ , thus not same as the original regEx.


Thus the answer should be none of these.

---

Just a little twist in option 1 as 1*(0.1*)* then it will be same as given in question.

---

110 cannot be generated by 1.

$(1^*0)^*1^*\supset (1^*0)^*\supset (1^*0)$

So $1^*0$ can be generated.

If we observe carefully , the string 11101110 is in RegEx Original,  but it is not possible in this regEx , thus both are not same.

You both are saying same thing that (1*0) is not generated..

What's wrong with me??

---

yes, (1) is same expression as given expression.

Answer 1

I think regular expression 1 is correct.

$\because \color{blue} {a^*(ba^*)^*=b^*(ab^*)^*=(a+b)^*}$

And one more important conversion--

$\color{cyan}{(PQ)^*P=P(QP)^*}$

From this we can write $a^*(ba^*)^*=(a^*b)^*a^*$

where P is a* and Q is b.

So in given question--

$0^*(10^*)^*=(1+0)^*=1^*(01^*)^*=(1^*0)^*1^*$

Option 1 is correct..