in Theory of Computation edited by
18,855 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

4 Comments

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

31 Comments

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

which option A can not produce
1
1

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

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

Similarly for 10001000

4
4
100 can be derived from A.

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

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

$$(1^*0)^*1^* = (1^*0)(1^*0)1^* = (10)(\epsilon 0)( \epsilon) = 100$$
8
8
well ,now i got how "100" is coming thnx :)
0
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
0
@Aditya

$(1^{*}0)^{*}1^{*} = (1^{*}0)^{1}1^{0} = 1^{*}0 = 1^{2}0 = 110 $
1
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
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
0
I think answer should be none of these.

Because given expression can generate 010  But option A can not generate 010.
0
0
yeah ! even i was thinking the same, 010 is not generated by option a.
0
0
@Shaik Masthan
0
0

@gate fever

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

4
4

yes u are right!Rishav Kumar Singh 

i didn't notice that!!

0
0
Are all reg ex questions just trial and error?
1
1
How to make sure that our regex generates the whole set?
0
0
For option A) 01110 will not be accepted , so option A should not be the ans
0
0
(1* 0)* 1*  can give 01110
0
0
Can the regular expresssion given in the question produce the string 101 ?
0
0
0*(10*)*  can produce 101
0
0

 0∗(10∗)∗   === is this can generate 101 or not ??

My approach was (10^1)^2 = gives 10 first then 1 combinely 101 is that so? 

2
2
yes
1
1
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