41 votes 41 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)^*$ Theory of Computation gate1998 theory-of-computation regular-expression easy multiple-selects + – Kathleen asked Sep 25, 2014 • edited May 15, 2018 by Milicevic3306 Kathleen 23.2k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Nirmal Gaur commented Jan 13, 2020 reply Follow Share 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 votes 0 votes Sagar78 commented May 7, 2020 reply Follow Share 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 votes 0 votes Ajitgate21 commented Oct 20, 2022 reply Follow Share Option A:- 110*(0+1)=>11(0)*(0+1)=>{11{0^0,0^1,0^2..}(0+1)}=>{11,110,1100...(0+1)}=>L={110,111,1101,11000,11001}. 1101 belong to the L. Option B:- 1(0+1)*101=>1{(0+1)^0,(0+1)^1...}101; 1(e,0,1)101=>{1101,1101….) 1101 belong to the L. Option C:- (10)*(01)*(00+11)*. (10)*={e,10,1010,..}. (01)*={e,01,0101,..}. (00+11)*={e,11,00,1100,0011,1111,0000...}=>L={e,10,1010,..,01,0101,..11,00,1100,0011,1111,0000, 100111,100111,…... }. 1101 Doesn’t belong to the L. Option D:-(00+(11)*0)*; (11)*={e,11,1111,...} (00+{e,11,1111,...}0)*=> (00+0,110,11110,...)*=>{e,00,0,000,00110,11000,110110,0000….}. 1101 Doesn’t belong to the L. Ans:- C and D. 0 votes 0 votes Please log in or register to add a comment.
Best answer 52 votes 52 votes 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$. Arjun answered Oct 3, 2014 • edited Jun 15, 2018 by Milicevic3306 Arjun comment Share Follow See all 29 Comments See all 29 29 Comments reply Gate Keeda commented Oct 10, 2014 reply Follow Share so your answer says that only C is right? I vote for C. 0 votes 0 votes Arjun commented Oct 10, 2014 reply Follow Share Both c and d are answers. d also cannot generate 1101 rt? 11 votes 11 votes Gate Keeda commented Oct 10, 2014 reply Follow Share So we have to look for 1101 as a whole? or we can take it from 11011? 2 votes 2 votes Arjun commented Oct 10, 2014 reply Follow Share As per question it must be 1101 as a whole. If question had "substring" then we could have taken 11011 as well. 22 votes 22 votes Abhishek Agrawal commented Nov 10, 2014 reply Follow Share in (d) how u can generate 11011.i dont think so plz correct me if i m wrong 0 votes 0 votes Arjun commented Nov 10, 2014 reply Follow Share (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 2 votes 2 votes Anu commented Jun 14, 2015 reply Follow Share In third step is it 110? 0 votes 0 votes Digvijay Pandey commented Jun 14, 2015 reply Follow Share 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)*.. 3 votes 3 votes anonymous commented Jun 16, 2015 reply Follow Share 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 0 votes 0 votes Arjun commented Jun 16, 2015 reply Follow Share In option d, no 01 rt? 1 votes 1 votes anonymous commented Jun 16, 2015 reply Follow Share yes in option d 01 is not there but what about option C first step: ∈ ∈ 11 second step: ∈01 ∈ string will be 1101 0 votes 0 votes Digvijay Pandey commented Jun 16, 2015 reply Follow Share ^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.. 4 votes 4 votes anonymous commented Jun 16, 2015 reply Follow Share suppose option C is ((10)*(01)*(00 + 11)*)* then is it possible to generate 1101 0 votes 0 votes Digvijay Pandey commented Jun 16, 2015 reply Follow Share ^Yes .. then it ll be (10 + 01 + 00 + 11)* i.e. any even length string accepted.. here order doesn't matter.. 2 votes 2 votes minal commented Jul 18, 2015 reply Follow Share does really order matters in every case ?? 0 votes 0 votes anonymous commented Jul 18, 2015 reply Follow Share concatenation is not commutative that's why order matters. 5 votes 5 votes Mridul Sachan commented Jan 23, 2016 reply Follow Share @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. 1 votes 1 votes Arjun commented Jan 23, 2016 reply Follow Share generate means it must be a string- not substring. 16 votes 16 votes rishi71662data4 commented Sep 14, 2017 reply Follow Share (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 votes 0 votes krati litoriya commented Sep 28, 2017 reply Follow Share 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 votes 0 votes air1ankit commented Dec 11, 2017 reply Follow Share sir can you please expend the option 4 ..i am not getting how to expend (11)* = ???? 0 votes 0 votes Aspirant commented Jan 6, 2018 i edited by Aspirant Jan 6, 2018 reply Follow Share 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 votes 0 votes suneetha commented Oct 6, 2018 reply Follow Share sir will you give finite automata's for this regular expressions? 0 votes 0 votes anchitjindal07 commented Dec 26, 2018 reply Follow Share @Arjun Sir which option to mark if such question comes in exam 0 votes 0 votes Rajesh Panwar commented Jul 28, 2019 reply Follow Share both c and d are right answer 0 votes 0 votes souveekp commented Oct 5, 2020 reply Follow Share 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 3 votes 3 votes Yawar Rmir commented Jun 13, 2021 reply Follow Share Answer should be option (C), as option (D) forces the string to end with 0 (zero). 1 votes 1 votes himanshud2611 commented Sep 17, 2023 reply Follow Share How (D) can generate “substring” 1101? @souveekp 0 votes 0 votes Rishabh shukla1006 commented Apr 9 reply Follow Share It can generate a string 110110 in which we have 1101 as substring..Check properly there is kleen closure operator on whole bracket in option (d). @himanshud2611 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 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. Mridul Sachan answered Jan 23, 2016 Mridul Sachan comment Share Follow See 1 comment See all 1 1 comment reply Rajesh Raj commented Jul 3, 2016 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes c and d both are right VOOTLA SRINIVAS answered Oct 10, 2014 VOOTLA SRINIVAS comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Bhagirathi answered Sep 26, 2014 Bhagirathi comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Oct 3, 2014 reply Follow Share That's right. But what about (c)? 4 votes 4 votes Please log in or register to add a comment.