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

I think in D we are not considering 11011 because its is generated as substring , correct me if i am wrong 

---

if its asked set of all strings which cannot generate 1101 then D is the answer

---

optoin A and B can give me 1101 directly, but rest can't give me 01 at the end.

Answer 1

Only (a) and (b) can generate $1101$.

In (c) after $11$, we can not have $01$ and so $1101$ cannot be generated.

In (d) Every $11$ followed by $0$ and no single occurrence of $1$ is possible. So it cannot generate $1101$ or $11011$.

Comments

How (D) can generate “substring” 1101? @souveekp

---

It can generate a string 110110 in which we have 1101 as substring..Check properly there is kleen closure operator on whole bracket in option (d). @himanshud2611

---

The catch is in the word "String", if the question said "Substring" then D would belong to the set, but we need string, which means a perfect match (that string and nothing else), a perfect match can be generated only by A and B, so it doesn't belong to C and D, so C and D are the answers.

Answer 2

I think option (c) is more appropriate to choose from, because even option (d) can generate 11011 or 110110 in which 1101 is a substring.

Comments

yeahh.  I think D  is not allowed because let  (00+(11)*0)*  can be written as (a+b)*
and we know 'bb'  is allowed in (a+b)* so in  (00+(11)*0)*  110110110...   is allowed. now see bold substring is 1101.

---

But asked about string 1101 but not as substring .

Answer 3

c and d both are right

Answer 4

option d is quite inviting to choose it as we can have only even number of 1's with this regular set where as our original string contains 3 1's

Comments

That's right. But what about (c)?

Answer 5

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

therefore both c and d are correct

Answer 6

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.