The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
3.7k 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)^*$
asked in Theory of Computation by Veteran (59.6k points)
edited by | 3.7k views
0
option d generate 110110, here 1101 is as substring so option d is valid or not???

5 Answers

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

answered by Veteran (361k points)
edited by
0
so your answer says that only C is right?

I vote for C.
+3
Both c and d are answers. d also cannot generate 1101 rt?
0
So we have to look for 1101 as a whole? or we can take it from 11011?
+6
As per question it must be 1101 as a whole. If question had "substring" then we could have taken 11011 as well.
0
in (d) how u can generate 11011.i dont think so

plz correct me if i m wrong
+1
(00 + (11)*0)* : In one step this can generate ϵ, 00, or any combination of 11 followed by 0. And * means this can go on to any number of steps.

First step : 11
Second step: 0
Third step: 11
0
In third step is it 110?
+2
Option D is (00 + (11)*0)* = (00 + 0 + (11)^+0)* //(11)* = (11)^+ + null
Every 11 followed by some 0..
String 11011 not in (00 + (11)*0)*..
0
a doubt cant we do like this in option c to generate string 1101

first step: *(selecting epsilon) * 11

second step: * 01 *

string will be 1101
+1
In option d, no 01 rt?
0

yes in option d 01 is not there but what about option C

 


first step: ∈ ∈ 11

second step: ∈01 ∈

string will be 1101
+3
^Order matters..

Step 1. (10)* take null from here.

Step 2. (01)* take null from here.

Step 3. (00+11)* take 11 from here.

Step 4. Here u may take (00+11)* but not (01)* or (10)*.. once u reached at (00+11)* u cant backtrack..
0

suppose option C is

((10)*(01)*(00 + 11)*)* then is it possible to generate 1101

+2
^Yes .. then it ll be (10 + 01 + 00 + 11)* i.e. any even length string accepted.. here order doesn't matter..
0
does really order matters in every case ??
+3
concatenation is not commutative that's why order matters.
+1
@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.
+10
generate means it must be a string- not substring.
0
(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
0
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..
0
sir can you please expend the option 4 ..i am not getting how to expend

(11)* = ????
0
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.
0
sir will  you give finite automata's for this regular expressions?
+5 votes
c and d both are right
answered by (335 points)
+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.

answered by (277 points)
0

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.

+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

answered by Boss (14.3k points)
+3
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

answered by Junior (787 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

42,295 questions
48,415 answers
153,524 comments
62,660 users