in Theory of Computation
366 views
1 vote
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? 

in Theory of Computation
by
366 views

4 Comments

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

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
yes, (1) is same expression as given expression.
0
0

1 Answer

1 vote
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..
selected by

Related questions