GATE CSE 1998 | Question: 1.12

Question

The string $1101$ does not belong to the set represented by

• A. $110^*(0 + 1)$
• B. $1(0 + 1)^*101$
• C. $(10)^*(01)^*(00 + 11)^*$
• D. $(00 + (11)^*0)^*$

Comments

Those having a problem while understanding how strings are generated using regular expressions, refer to:

http://www.fbeedle.com/formallanguage/ch07.pdf (First 4 pages)

---

I think D is the correct ans.. 

The string 1101

In opt A it is generated.. 

In opt B it is generated.. 

In opt C if we reverse the string i..e 1011 then it generated.. 

In op D neither 1101 or 1011 is generated.. Hence it is the ans... 

Correct m if I am wrong..  

---

Option A:- 110*(0+1)=>11(0)*(0+1)=>{11{0^0,0^1,0^2..}(0+1)}=>{11,110,1100...(0+1)}=>L={110,111,1101,11000,11001}. 1101  belong to the L.

Option B:- 1(0+1)*101=>1{(0+1)^0,(0+1)^1...}101; 1(e,0,1)101=>{1101,1101….) 

1101  belong to the​​​​​​​ L.

Option C:- (10)*(01)*(00+11)*.

(10)*={e,10,1010,..}. (01)*={e,01,0101,..}. (00+11)*={e,11,00,1100,0011,1111,0000...}=>L={e,10,1010,..,01,0101,..11,00,1100,0011,1111,0000, 100111,100111,…...  }. 1101  Doesn’t belong to the​​​​​​​ L. 

Option D:-(00+(11)*0)*; (11)*={e,11,1111,...}

(00+{e,11,1111,...}0)*=> (00+0,110,11110,...)*=>{e,00,0,000,00110,11000,110110,0000….}. 1101  Doesn’t belong to the​​​​​​​ L.  Ans:- C and D.

Answer 1

from option c and d we can't generate string 1101.

therefore both c and d are correct

Answer 2

Here point to keep in mind is, question is asking string not substring, means given RE should not generate 1101 as string. If we look at option d, it will generate either no 1 or even no. of 1's always & can't generate odd no. of 1's. Hence D is the answer.

Answer 3

c and d both are right

So,No need much think about which one is more correct and which one to choose because both are equally correct & if we take 1101 as substring (instead of string in question) then c will be answer but  should we correct that?

I think we should not apply over logic in correcting question and if such a ambiguity arise now a day they will give marks to all.