The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
2.8k views

The regular expression $0^*(10^*)^*$ denotes the same set as

  1. $(1^*0)^*1^*$
  2. $0+(0+10)^*$
  3. $(0+1)^*10(0+1)^*$
  4. None of the above
asked in Theory of Computation by Veteran (59.6k points)
edited by | 2.8k views
0
0*(10*)*

a=0  b=1

a*(ba*)* =(a+b)* =(0+1)* which generates all possible strings over 0 and 1

option A : (1*0)*1*  

if i have to generate 010 then how can we generate from option A but it can be generated by given regular expressions.

plz correct me where i m wrong......

@Bikram sir
0
@akash

How you write a*(ba*)* =(a+b)*  ?

we have to generate 100 from option A as  given RE generate 100  not 010 .
+2
@Bikram sir
this is kind of identity which we use in regular expressions.

we know this thing right!!!

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

the question is  0*(10*)*, so by using above identity, I can write or convert this into (0+1)*. which means set of all strings over  0 and 1 are possible under this regular expression, right!!! so this expression will contain this string 010 also.

but option A is (1*0)*1*, how can i generate 010 from this expression.

@Bikram sir hope u get me
+2

akash.dinkar12 

yes, i understand , 

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

now a*(ba*)* = (a*b)* a *   .....(i)      so put a=0  b=1 and we get  (0*1)*0* 

given   0*(10*)*  = (0*1)*0* =  (0* 1) (0* 1) 0*  =  (0 1 )  (ϵ 1) ϵ  = 011    [ by putting 0* = ϵ ]      it generates all strings over Σ . Where Σ =(0,1) 

now option A,    (1*0)*1*  = (1* 0) (1* 0)  1* = ( 1 0) (ϵ 0) ϵ    = 100         [ by putting 1* = ϵ ] this also generates all strings over Σ .  where Σ = (0,1) 

so thats why 0* (1 0*)* =  (1* 0)* 1*  because from both we can get all strings of 0 and 1 generates over Sigma .

PS: There is no way we can directly show  0*(10*)* = (1*0)*1* ...  we need to generate strings and compare are both same or not !

Hope you are getting my point .

+1
if  Σ = (0,1) then all strings over  Σ = 00 , 11, 01,10  ..... etc
+1

akash.dinkar12 

but option A is (1*0)*1*, how can i generate 010 from this expression.

1*0 1*0   ϵ  -->  ϵ01*0 --> 010

0
thanx VS
+2
(a+b)* = (a*b)*a* = a*(ba*)* = b*(ab*)* = (b*a)* b*

we can understand them in an intuitive manner by taking any one of them as example :

lets take (a*b)*a* : in this (a*b)* will generate all type of strings on {a,b} except those ending with 'a' and thus for including them also we take a* in ending. Similarly, in b*(ab*)* , (ab*)* will generate all strings on {a,b} except those starting with 'b' and thus we'll prefix b* to it...
+2

 akash.dinkar12  this is also an identity:

P(QP)*=(PQ)*P

0
what is the possible pattern for (0+1)*, i want the pattern up to the string length 4?

8 Answers

+27 votes
Best answer
  1. Is the answer. Both (A) and the given expression generates all strings over $\Sigma$.
  2. doesn't generate $11$
  3. doesn't generate $11$
answered by Veteran (359k points)
edited by
+1
man its very hard to recognize that those 2 expression generate the whole set :(
+3
If we see in the given expression, any number of 0 can come in beginning followed by any number of 1 and this can be repeated any number of times. Thus we can conclude they generate all strings. In option (A) also, this happens. Not s systematic approach, but not difficult to realize with a few tries of combinations.
+1
why not ans d   the given expression  can produce 100100  10001000 and similar exp

which option A can not produce
+2

Option A can produce 100100 (when the 1* at the end generates ϵ)

(1*0)*
=> 1
=>10
=>100
=>1001
=>10010
=>100100

Similarly for 10001000

+1
100 can be derived from A.

(1*0) ->1
(1*0) (1*0) -> 10
(1*0) (1*0) (1*0) -> 100
0
Yes . you are right. I didn't look at problem this way.

This problem need special care.
+6
yes because P(QP)* = (PQ)*P
here P= 0*, Q= 1
0*(10*)* = (0*1)*0*
0
I couldn't understand the logic for the derviation

100 can be derived from A.

(1*0) ->1
(1*0) (1*0) -> 10
(1*0) (1*0) (1*0) -> 100
+1
how 1* 0 =>1 and not 0 or 10 or 110
+5
@biranchi

$$(1^*0)^*1^* = (1^*0)(1^*0)1^* = (10)(\epsilon 0)( \epsilon) = 100$$
0
well ,now i got how "100" is coming thnx :)
0
option A is  NOT generating string 110 ,whereas the given regular expression can generate string 110...

So,the correct answer should be D.
+1
@Aditya

$(1^{*}0)^{*}1^{*} = (1^{*}0)^{1}1^{0} = 1^{*}0 = 1^{2}0 = 110 $
0
Sir, can 010001000 which can be generated by the given expression but it cannot be generated by (A). Corrrect me if I am wrong
0
@Arjun

Can below justification valid that

0*(10*)* = (0+1)* [according to identity] here a=0, b=1

and (1*0)*1* = (1+0)* [according to identity] here a=1, b=0.

As both are coving all strings over (0+1)* no matter a and b are different, they are equivalent REs.
0
I think answer should be none of these.

Because given expression can generate 010  But option A can not generate 010.
0
yeah ! even i was thinking the same, 010 is not generated by option a.
0
@Shaik Masthan
+7 votes

Start with the minimum length strings , like - strings of length 0 , strings of length 1... and check with the options and eliminate those that dont match.

Given string accepts empty string , but the options B) and C) do not accept empty string. They are eliminated.

Now the given regular expression and A) accept all strings over 0 and 1.
Testing all strings of length 0 , 1 , 2 and 3.. proves it to be true.

Can there be a formal way to show that these regular expressions are exactly the same?
 
 
answered by Active (3.7k points)
+2
Formal method is mentioned in texts rt? But I think what you told is more practical for solving questions. Formal method here helps in writing a code, but it's time consuming with human mind.
0
(1*0)*1*

(1*0) (1*0) (1*0) 1*

Put 0 in first star of (1*0) then put 0 again in second stare of (1*0) now put 1 in place of 3rd stare of(1*0) and finally 0 in place of last star .

(Eps 0) (Eps 0) (1 0) eps
0
001100 is valid for both the string?? plz clearfiy me??
0
@arjun sir

I think B can accept  empty string . is it right?
+1
@sittian yes, it does.
0
But option B cant accept 1. Thus B is wrong
+2 votes
B) can not generate 01 and

C) can not generate 00

so option A is the correct answer
answered by Loyal (7.8k points)
+1 vote
In 0*(10*)*, (10*)* generates all strings on {0,1} except those starting with 0. So if we prefix 0* also then it will include those also. And thus this regex implies (0+1)*.

And now we can see option a in similar way. In (1*0)*1*, (1*0)* generates all strings except those ending with 1, so we prefixed 1* in end. Hence this also follows (1+0)*. Hence option A is the right answer
answered by Active (1.7k points)
0 votes
option A is generating string 110 ,whereas the given regular expression cannot generate string 110...

So,the correct answer should be D.
answered by Junior (887 points)
0 votes
Given regular expression is  0*(10*)*

A: (1*0)*1*
All strings that can be generated from given regular expression
can also be generated from this.

B: 0 + (0 + 10)*  and C: (0 + 1)* 10(0 + 1)*
We can generate  11 from given regular expression which is not 
possible with B and C

C: (0 + 1)* 10(0 + 1)*
Not possible as we can produce {epsilon} from the given Regular 
Expression but not from C
answered by Junior (563 points)
0 votes

option (A) and the given expression generates string 1

but option b anc c is not genrate 

answered by Boss (23.9k points)
–1 vote
A as only one is accepting the null while others are not. Nd 1 is accepting all strings
answered by Boss (16k points)
0
We cannot comment anything about D option,it may accept NULL
0
Option B is accepting Null
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,078 questions
47,675 answers
147,462 comments
62,393 users