16,833 views

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

1. $110^*(0 + 1)$
2. $1(0 + 1)^*101$
3. $(10)^*(01)^*(00 + 11)^*$
4. $(00 + (11)^*0)^*$

option d generate 110110, here 1101 is as substring so option d is valid or not???
No. 1101 as a string must belong to the set.

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

### Subscribe to GO Classes for GATE CSE 2022

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

by

@Arjun Sir which option to mark if such question comes in exam
both c and d are right answer

If the question says about "string" 1101 then both option C and D can't generate. But if question was trying to ask about "substring" then only option C is correct as it can't generate 1101

Answer should be option (C), as option (D) forces the string to end with 0 (zero).

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.

### 1 comment

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.

c and d both are right

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

### 1 comment

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

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

therefore both c and d are correct

by