in Theory of Computation edited by
11,140 views
47 votes

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
in Theory of Computation edited by
11.1k views

16 Comments

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
1
@akash

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

we have to generate 100 from option A as  given RE generate 100  not 010 .
0
@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 .

2
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

3
thanx VS
0
(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...
11

 akash.dinkar12  this is also an identity:

P(QP)*=(PQ)*P

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

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

3

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

6

@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
0

From option C we can never get Epsilon, hence can be ruled out easily. 

0
P(QP)* = (PQ)*P
here P= 0*, Q= 1
0*(10*)* = (0*1)*0*
0

Subscribe to GO Classes for GATE CSE 2022

10 Answers

42 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$
edited by
by

22 Comments

man its very hard to recognize that those 2 expression generate the whole set :(
6
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.
8
why not ans d   the given expression  can produce 100100  10001000 and similar exp

which option A can not produce
1

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

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

Similarly for 10001000

3
100 can be derived from A.

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

This problem need special care.
0
yes because P(QP)* = (PQ)*P
here P= 0*, Q= 1
0*(10*)* = (0*1)*0*
9
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
0
how 1* 0 =>1 and not 0 or 10 or 110
2
@biranchi

$$(1^*0)^*1^* = (1^*0)(1^*0)1^* = (10)(\epsilon 0)( \epsilon) = 100$$
8
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.
0
@Aditya

$(1^{*}0)^{*}1^{*} = (1^{*}0)^{1}1^{0} = 1^{*}0 = 1^{2}0 = 110 $
1
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
0

@gate fever

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

2

yes u are right!Rishav Kumar Singh 

i didn't notice that!!

0
Are all reg ex questions just trial and error?
0
How to make sure that our regex generates the whole set?
0
15 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?
 
 

6 Comments

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.
8
(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
reshown by
@arjun sir

I think B can accept  empty string . is it right?
0
@sittian yes, it does.
1
But option B cant accept 1. Thus B is wrong
0
4 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
by
2 votes

According to regular identity refer point 14  https://cs.uwaterloo.ca/~nishi/360W16/Resources/identities.pdf

In the question given regular expression equals to (0+1)^*      

Now lets look at option A, this regular expression equals to (1+0)^*

(0+1)^* equals (1+0)^* so A is the answer

1 vote
B) can not generate 01 and

C) can not generate 00

so option A is the correct answer
1 vote
Can we do it like this,

In the given RE,

0*(10*)*

If we put *= epsilon, it generates nothing.

But in option A and C if we put * =epsilon, they generate 0 and 10 respectively ,

So, we can say that option A is correct
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
0 votes

option (A) and the given expression generates string 1

but option b anc c is not genrate 

2 Comments

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.

0
we can declare by only one string also
–1
0 votes
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
0 votes

This Question is very simple, Only thing we do approaches to the problem in wrong way.

L = 0*(10*)* : To do this type of problem always expand * As precedence of operator is [(*) >( .) > (+)]. Now you will never do this wrong.

hence the L =  0*(10*)* can be expanded like this ->

= 0*{ e + (10*) + (10*)(10*) + (10*)(10*)(10*) +..........}

Now after this just take Alphabet(A) = { 0, 1} and find the what are the strings present in A* or {0,1} * can also be obtain by L = 0*(10*)*.

You will find that L = {0, 1} * = A *.( Which is also a STANDARD RESULT, if you want, you can remember this)

 Ex -  We can generate 100 from L by doing like this -> 0*(10*) = e.(100) = 100.

SIMILARLY by doing the same way,

M = (1*0)*1* 

= {e + (1*0) + (1*0)(1*0) + (1*0)(1*0)(1*0) + ..........} 1*  

By doing the same way you can easily find that it is also equal to {0,1}* or A*. 

Ex - We can also generate 100 from M also in this way -> just take (1*0)(1*0) = (10)(1*0) = (10)(0) = 100.

Hence Both M and L are equal . 

 

 

Answer:

Related questions