The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
1.9k 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 (69k points) | 1.9k views
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
@akash

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

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 .

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

akash.dinkar12 

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

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

 

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

 akash.dinkar12  this is also an identity:

P(QP)*=(PQ)*P

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

7 Answers

+26 votes
Best answer
(A) is the answer. Both (A) and the given expression generates all strings over $\Sigma$.

(B) doesn't generate 11

(C) doesn't generate 11
answered by Veteran (346k points)
selected by
man its very hard to recognize that those 2 expression generate the whole set :(
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

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

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

Similarly for 10001000

 

100 can be derived from A.

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

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

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

So,the correct answer should be D.
@Aditya

$(1^{*}0)^{*}1^{*} = (1^{*}0)^{1}1^{0} = 1^{*}0 = 1^{2}0 = 110 $
Sir, can 010001000 which can be generated by the given expression but it cannot be generated by (A). Corrrect me if I am wrong
+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?
 
 

 

answered by Loyal (3.7k points)
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.
(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
001100 is valid for both the string?? plz clearfiy me??
@arjun sir

I think B can accept  empty string . is it right?
@sittian yes, it does.
+2 votes
B) can not generate 01 and

C) can not generate 00

so option A is the correct answer
answered by Boss (8.3k points)
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
answered by Active (1.3k 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 Active (1.2k 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 (553 points)
–1 vote
A as only one is accepting the null while others are not. Nd 1 is accepting all strings
answered by Veteran (15.8k points)
We cannot comment anything about D option,it may accept NULL
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

33,687 questions
40,231 answers
114,271 comments
38,803 users