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

Dark Mode

srestha
asked
in Theory of Computation
Apr 11, 2019

366 views
1 vote

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?

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??

1

1 vote

Best answer

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..

$\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..