The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

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

- $110^*(0 + 1)$
- $1(0 + 1)^*101$
- $(10)^*(01)^*(00 + 11)^*$
- $(00 + (11)^*0)^*$

+35 votes

Best answer

+6

As per question it must be 1101 as a whole. If question had "substring" then we could have taken 11011 as well.

+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

First step : 11

Second step: 0

Third step: 11

+3

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

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

first step: *(selecting epsilon) * 11

second step: * 01 *

string will be 1101

0

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

first step: ∈ ∈ 11 second step: ∈01 ∈ string will be 1101 |

+4

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

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

+2

^Yes .. then it ll be (10 + 01 + 00 + 11)* i.e. any even length string accepted.. here order doesn't matter..

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

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

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

+5 votes

**1101**1 or **1101**10 in which 1101 is a substring.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,634 questions

52,769 answers

183,405 comments

68,307 users