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

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