in Theory of Computation edited by
18,857 views
56 votes
56 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
18.9k views

18 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
2
2
@akash

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

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

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 .

3
3
if  Σ = (0,1) then all strings over  Σ = 00 , 11, 01,10  ..... etc
1
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

4
4
thanx VS
0
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...
13
13

 akash.dinkar12  this is also an identity:

P(QP)*=(PQ)*P

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

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

3
3

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

8
8

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

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

1
1
P(QP)* = (PQ)*P
here P= 0*, Q= 1
0*(10*)* = (0*1)*0*
2
2
010 is generated by the expression in the question but how it will be generated by option a
1
1
areey take (1*0)*1*   as   (1*0)(1*0) = (0)(10) = 010...tadaaa

Inshort (1*0) taken 2 times and 1* taken as Epsilon.
1
1

12 Answers

49 votes
49 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

4 Comments

0*(10*)* can produce 1111... so how can option (A) produce 1111?
0
0

@deeptadas here is the explanation. If you have any queries then feel free to ask.

0
0
we can directly show that a*(ba*)* =(b*a)*b* = (a+b)*.

Expand LHS as a*[ ε + ba* + ba*ba* + ba*ba*ba* + ….]

a* + a*ba* + a*ba*ba* + a*ba*ba*ba* + ….

a*= strings containing zero b.

a*ba* = strings containing exactly one b.

a*ba*ba*=strings containing exactly two b.

So all the strings are generated.

Similarly we can expand (b*a)*b* = [ ε + b*a + b*ab*a….]b*

= b*  + b*ab* + b*ab*ab* + ….

b*= strings containing zero a.

b*ab*=strings containing exactly one a

b*ab*ab*=strings containing exactly two a

So it also generates all strings.

Hence a*(ba*)* =(b*a)*b* = (a+b)*.
0
0
17 votes
17 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?
 
 

4 Comments

reshown by
@arjun sir

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

Answer:

Related questions