The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+28 votes

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

- $(1^*0)^*1^*$
- $0+(0+10)^*$
- $(0+1)^*10(0+1)^*$
- None of the above

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

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

@akash

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

we have to generate 100 from option A as given RE generate 100 not 010 .

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

we have to generate 100 from option A as given RE generate 100 not 010 .

@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

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

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 .

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

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

akash.dinkar12 this is also an identity:

**P(QP)*=(PQ)*P**

+26 votes

Best answer

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.

why not ans d the given expression can produce 100100 10001000 and similar exp

which option A can not produce

which option A can not produce

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

(1*0)*

=> 1

=>10

=>100

=>1001

=>10010

=>100100

Similarly for 10001000

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

100 can be derived from A.

(1*0) ->1

(1*0) (1*0) -> 10

(1*0) (1*0) (1*0) -> 100

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

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?

0 votes

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

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

0 votes

option A is generating string 110 ,whereas the given regular expression cannot generate string 110...

So,the correct answer should be D.

So,the correct answer should be D.

0 votes

A: (1*0)*1*All strings that can be generated from given regular expression can also be generated from this.B: 0 + (0 + 10)*andC: (0 + 1)* 10(0 + 1)*We can generate 11 from given regular expression which is not possible with B and CC: (0 + 1)* 10(0 + 1)*Not possible as we can produce {epsilon} from the given Regular Expression but not from C

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users