2 votes 2 votes "A regular expression denoting a language (set of strings) means it should generate all string in L and not generate any string not in L" L is set of all strings not containing 100 as substring? Theory of Computation theory-of-computation + – hem chandra joshi asked Nov 14, 2017 hem chandra joshi 372 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Rohit Gupta 8 commented Nov 14, 2017 reply Follow Share ((10+1)*+(01+1)*+0*1*)(010)* 0 votes 0 votes hem chandra joshi commented Nov 14, 2017 reply Follow Share I am asking simplification of above statement buddy . Please go through it . 0 votes 0 votes Rohit Gupta 8 commented Nov 14, 2017 i edited by Rohit Gupta 8 Nov 14, 2017 reply Follow Share Given Language L : set of all strings not containing 100 as substring. Think of L as set containing $\left\{0,1,00,01,10,11,000,001,010,011,101,110,111......\right\}$ It means the sel L contains string, which does not contain 100 as substring in it. So regular expression denoting this language should generate exactly those string contained in the set L and should not generate those which does not belongs to set L. Strings that does not belong to this set are $S = \left\{100, 0100, 1100, 01000,10000, 10100, 11000 .....\right\}$. The set S have all string of pattern $(0+1)^*100(0+1)^*$ which does not belong to L. It is compliment of L. 1 votes 1 votes Please log in or register to add a comment.