in Theory of Computation edited by
16,833 views
32 votes
32 votes

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)^*$
in Theory of Computation edited by
16.8k views

4 Comments

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

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)

0
0

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

Subscribe to GO Classes for GATE CSE 2022

7 Answers

49 votes
49 votes
 
Best answer

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

edited by
by

5 Comments

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

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

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

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.

0
0
5 votes
5 votes
c and d both are right
2 votes
2 votes

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)?
3
3
1 vote
1 vote

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

therefore both c and d are correct

Answer:

Related questions