8 votes 8 votes Over the alphabet $\{0, 1\}$, consider the language $L = \{ w | \: w \text{ does not contain the substring } 0011\}$ Which of the following is true about $L$. $L$ is not context free $L$ is regular $L$ is not regular but it is context free $L$ is context free but not recursively enumerable Theory of Computation cmi2010 theory-of-computation identify-class-language + – go_editor asked May 19, 2016 edited Feb 20, 2018 by kenzou go_editor 1.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply Punit Sharma commented Aug 22, 2019 reply Follow Share make the DFA for containing 0011 as a substring ...then compliment it .. As DFA exists it will be regular...Also Regular lang.s are closed under complimentation.. 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Let L1 be (0+1)*. L1 is regular. Let L2 be Strings containing 0011 is regular. (0+1)*0011(0+1)* L1 - L2 = Regular. (Regular languages are closed under Difference). Correct Answer: $B$ ashoklb answered Feb 2, 2018 edited May 9, 2019 by Naveen Kumar 3 ashoklb comment Share Follow See all 0 reply Please log in or register to add a comment.
5 votes 5 votes (B) $L$ is regular. Praveen Saini answered May 19, 2016 edited Feb 20, 2018 by kenzou Praveen Saini comment Share Follow See all 3 Comments See all 3 3 Comments reply iarnav commented Nov 1, 2017 reply Follow Share @Praveen Saini Sir, please explain how. I'm indeed a dire fan of your explanations. We can see, option d) is False b/c every CFL is REC and indeed R.E but please explain the approach how it's Regular P.S - we can make DFA which doesn't accept substring "0011" does it make L regular?! @LeenSharma @manu00x you too may comment. 1 votes 1 votes Praveen Saini commented Nov 1, 2017 reply Follow Share Yes L is regular bcoz of same reason you mentioned. We can design FA for given L. So B is correct. L is regular, so it is CFL, CSL, rec and re too. That makes other options incorrect. 7 votes 7 votes iarnav commented Nov 1, 2017 reply Follow Share Thank You, Sir! :) 0 votes 0 votes Please log in or register to add a comment.