22 votes 22 votes Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$. Theory of Computation gate1987 theory-of-computation regular-expression descriptive + – makhdoom ghaya asked Nov 14, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 5.5k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply akash.dinkar12 commented Jul 30, 2017 i reshown by akash.dinkar12 Dec 24, 2018 reply Follow Share I think regular expression would be:(0+1+01+10+11+011+110) 16 votes 16 votes Manu Thakur commented Nov 29, 2017 reply Follow Share eps won't be included as eps is null string. 1 votes 1 votes air1ankit commented Dec 11, 2017 reply Follow Share what is the proper meaning of non null sub string ? 0 votes 0 votes bhuv commented Jan 4, 2018 reply Follow Share is 0110 a substring of 0110 or not? 0 votes 0 votes Verma Ashish commented Sep 5, 2018 reply Follow Share 0110 is not a proper substring of 0110 but it is a substring. So eps and 0110 are excluded. 1 votes 1 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes $0,1,01,10, 11 ,011 , 110$ $ \therefore \text{RE} : (0+1+01+10+11 +011 +110 )$ $\varepsilon$ and $0110$ are not part of RE because of NON-NULL and PROPER substring requirement. saxena0612 answered Dec 19, 2017 • edited Apr 15, 2021 by Lakshman Bhaiya saxena0612 comment Share Follow See all 2 Comments See all 2 2 Comments reply suryaprakash commented Jun 13, 2018 reply Follow Share can we use CYK algorithm here , event though it is given REGULAR. but every REGULAR is CFL ,can we use CYK????? but it takes much more time 1 votes 1 votes KUSHAGRA गुप्ता commented Dec 3, 2019 reply Follow Share # of substring: $\dfrac{n(n+1)}{2}+1=11$ Remove $0110$ $\&$ $\epsilon$ string as they have asked only proper non-null sub-strings. So let's write down 9 substrings: $0,1,1,0:$ $01,11,10$ $011,110$ Some of them are repeating. Hence we have to remove them. Resulting us just with 7 sub-strings: $0,1,01,11,10,011,110$ 5 votes 5 votes Please log in or register to add a comment.
9 votes 9 votes L = {0,1,01,11,10,011,110} R.E = 0(ε+1+11) + 1(ε+0+1+10) Soumya29 answered Oct 2, 2017 Soumya29 comment Share Follow See all 3 Comments See all 3 3 Comments reply Nitesh Singh 2 commented Dec 6, 2018 reply Follow Share with above R.E we can also generate 011110 which is not a substring. are you sure of your answer? 0 votes 0 votes Soumya29 commented Dec 6, 2018 reply Follow Share You can't generate 011110 from it. Try to make DFA , you will get it. This R.E is same as the one given in the best answer but in succinct form. 0 votes 0 votes Nitesh Singh 2 commented Dec 6, 2018 reply Follow Share oh! i misunderstood "+" sign in between of both expression and thought it is concatenation so end up deriving wrong string.🤔 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes $\varepsilon ^*0110\varepsilon ^*$ BILLY answered Mar 12, 2017 • edited Mar 12, 2017 by BILLY BILLY comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 0(E+1+11)+1(E+0+10) Navnit Kumar 2 answered Aug 30, 2017 Navnit Kumar 2 comment Share Follow See 1 comment See all 1 1 comment reply LeenSharma commented Oct 18, 2017 reply Follow Share sub-string 11 cannot be accepted from your R.E.Substring 11 should be accepted by R.E. 0 votes 0 votes Please log in or register to add a comment.