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.3k 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 Show 26 previous comments 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.