The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 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)^*$

+36 votes

Best answer

+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.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,122 questions

53,241 answers

184,705 comments

70,480 users