GATE CSE 2003 | Question: 14

Question

The regular expression $0^*(10^*)^*$ denotes the same set as

• A. $(1^*0)^*1^*$
• B. $0+(0+10)^*$
• C. $(0+1)^*10(0+1)^*$
• D. None of the above

Comments

i just thought about null and eliminated rest of the options.

---

i think it's sandwich property, hope all goclasses students know it.

---

(D) NONE should be the answer.
See, 0*(10*)* can generate null string,0*,1*,...
but  A) (1*0)*1  cant generate null string and 1*
Similarly option B and C fail to generate null string so its obvious in option there is no set that matches the equivalent set of the question.

Answer 1

• 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$

Comments

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)*.

---

given expression can generate string 100 but option A cannot generate it right ? anyone explain this plz

---

option A can give 100  (1*0)* =(10)(0)

Answer 2

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?
 

 

Comments

@sittian yes, it does.

---

But option B cant accept 1. Thus B is wrong

---

But here option A can gerate more string which are also can ends with 1* but given expression can't do it but they ask same set as expression then what to do option A) > given regular expression

Answer 3

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

Answer 4

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 5

B) can not generate 01 and

C) can not generate 00

so option A is the correct answer

Answer 6

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 .