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

edited | 3.8k views
+1
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

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
+2

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
+6
(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...
+4

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

Thanks @AakS, yours is the only explanation that explains why the two expressions are equivalent.

+4

we can see this identity P(QP)*=(PQ)*P  with help of this nfa

0

@Bikram sir

Can I say like this -

let * = 2(outer only)

now 0*(10*)* = 0*10*10*   &  (1*0)*1* = 1*01*01*

In both the case if we interchange 0 & 1 position then we can derive one from other.

So they are equal.

0
@MRINMOY_HALDER

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 . but option A is (1*0)*1*,

how can i generate 010 from this expression. 1*0 1*0 ϵ --> ϵ01*0 --> 010

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$
by Veteran (418k points)
edited
+1
man its very hard to recognize that those 2 expression generate the whole set :(
+5
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
+3

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.
+7
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
+6
@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

$(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
+1

@gate fever

(1*0)*1* = (1*0)(1*0) 1* = (E0)(10)E = 010.

0

yes u are right!Rishav Kumar Singh

i didn't notice that!!

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?

by Active (3.8k points)
+3
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
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
by Active (1.8k points)
+1 vote
B) can not generate 01 and

C) can not generate 00

so option A is the correct answer
by Loyal (7.8k points)
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
by Junior (567 points)

option (A) and the given expression generates string 1

but option b anc c is not genrate

by Boss (34.6k points)
0

option (A) and the given expression generates string 1

But only by comparing single string we can't declare that two regular expressions are same.

–1
we can declare by only one string also
B and C are not giving me choice on no of 1's. They are providing 10 as packs. So leave them.

Option A is good
by Junior (883 points)

1
2