The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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 by Veteran (52.1k points)
edited by | 4.4k views
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.

7 Answers

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

by Veteran (416k points)
edited by
concatenation is not commutative that's why order matters.
@Arjun Sir (d) can generate 1101 through (00+(11)*0)*. As firstly it will choose 11 from (00+11) then it will got 0, so at this time string will become 110 and similarly again it will repeat the same, so string will become 11011 or 110110 which contains 1101 as a substring. Correct me if I am wrong.
generate means it must be a string- not substring.
(00 + (11)*0)*
Let us write this as (00 + (11)*0) (00 + (11)*0) by taking * = 2
Now, let me choose the second part of each of this i.e. (11)*0(11)*0 = 110110
110110 is a string and 1101 is a substring of 110110. Therefore D is incorrect.

Thank you Arjun Sir
sir  in optn D "1101" as a substring is generated.. b'cz if for whole* I'm putting 2 and both time I'm selecting( (11)*0) * then 110110 is coming  as a string and 1101 is a substring over here..
sir can you please expend the option 4 ..i am not getting how to expend

(11)* = ????
Sir, I think option a can't be true .. Even though it generates 1101 but in worst case option a can generate 110 or 111 (by taking * as 0 ).

Sir, in exam should I assume worst case or just solve normally ? plz help.
sir will  you give finite automata's for this regular expressions?
@Arjun Sir which option to mark if such question comes in exam
both c and d are right answer
+5 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.

by (277 points)

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.

+4 votes
c and d both are right
by (333 points)
+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

by Boss (14.3k points)
That's right. But what about (c)?
0 votes

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

therefore both c and d are correct

by Junior (913 points)
0 votes

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 is the answer.

by (325 points)
0 votes
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.
by (169 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,839 questions
54,799 answers
80,674 users