6 votes 6 votes L1= Set of all strings having equal number of 00 and 11. L2= Set of all strings having equal number of 01 and 10. (a) Both are Regular (b) Both are Context-Free (c) L1 is regular, L2 is Context Free (d) L1 is CF, L2 is Regular Theory of Computation theory-of-computation regular-language + – Deepak Sharma 1 asked Aug 18, 2015 • retagged Jul 4, 2017 by Arjun Deepak Sharma 1 6.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 13 votes 13 votes L1 is well known Non Regular i.e. (00)^n(11)^n. (Since there is no common character in "00" and "11" we need to keep count of both which is not possible with a finite automata as count can be infinite). L2 is regular and its regular Expression like 0(0+1)*0 + 1(1+0)*1 + 1 + 0 +epsilon. Digvijay Pandey answered Aug 18, 2015 • selected Aug 18, 2015 by Pooja Palod Digvijay Pandey comment Share Follow See all 15 Comments See all 15 15 Comments reply Mojo-Jojo commented Aug 18, 2015 reply Follow Share Why wouldn't the regular expression ((0011)+(1100))* work for L1 ? 1 votes 1 votes Aditya commented Aug 19, 2015 reply Follow Share @Hodor Your regex says every 00 should be followed by 11 and every 11 should be followed by 00.. But that is not the case with given language.. 0 votes 0 votes Praveen Saini commented Aug 19, 2015 reply Follow Share @ Hodor , we cannot have 01100 or 01010011 from your regular expression , actually your regular expression is subset of " Equal no of 00's and Equal no of 11's" @Laser , actually 00n11n is also subset of "equal no of 00's and equal no of 11's" similarly anbn , bnan, (ab+ba)* all are subset of language "Equal-Equal" ( that is CFL , not regular) 1 votes 1 votes Digvijay Pandey commented Aug 19, 2015 reply Follow Share @Praveen sir : m not getting u 0 votes 0 votes Praveen Saini commented Aug 19, 2015 reply Follow Share Equal no of 00 and Equal no of 11 , also contain strings such that 1100, 0101100, 001011, etc actually 00n11n is also subset of "equal no of 00's and equal no of 11's" , And Yes for sure , it is non regular . 1 votes 1 votes Mojo-Jojo commented Aug 19, 2015 reply Follow Share @Aditya "Set of all strings having equal number of 00 and 11" There is no mention of order. You can't compare it with anbn . 0 votes 0 votes Digvijay Pandey commented Aug 19, 2015 reply Follow Share ^^ ohh. L = { w | w belongs to (0+1)* and n(00) = n(11) } 0 votes 0 votes abby murali commented Oct 31, 2015 reply Follow Share Just for clarification... The string 010 ⊂ L2 ..so are we counting '1' twice...like 01, 10 0 votes 0 votes radha gogia commented Jan 29, 2016 reply Follow Share Sir , If we have strings like 0101100, 001011 , so then how will we make a pda for it , whenever we will see a 0 or 1 , we will push it , so now when will the pop operations be performed , since here we can't keep a track of actually when we have seen 00 or 11 , since after 0 some 1 could have come ,plz give the logic for accepting it through pda. 0 votes 0 votes Praveen Kumar B commented May 21, 2017 reply Follow Share @Digvijay, can yu exlpain on L2, how is it regular ? 0 votes 0 votes LeenSharma commented May 22, 2017 reply Follow Share Praveen Kumar B Regular Expression for $L=(0(0+11^{*}0)^{*} + 1(1+00^{*}1)^{*}+\epsilon )$ and this is the DFA for given language. If you can draw a DFA for any language it means the language is regular. 3 votes 3 votes Praveen Kumar B commented May 22, 2017 reply Follow Share LeenSharma can you explain me on this Regular expression? 0 votes 0 votes amitqy commented Aug 9, 2018 reply Follow Share can you give an example in which a common character is present and is regular? 0 votes 0 votes Avinash virat commented Oct 12, 2018 reply Follow Share For L2 , according to the given answer it accept string 0, 00 etc. But 0, 00 doesn't belongs to language L2. Then how can we say that L2 is regular. 0 votes 0 votes DarshitGandhi commented Apr 15, 2020 reply Follow Share @Digvijay we cannot generate 01101001 with your regular expression....so i think that it is not a valid regex 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes this prob is solved before . ans will be d) L2 can be considered as all of the stings start and with same elements (0 or 1 ) Pranay Datta 1 answered Nov 6, 2015 Pranay Datta 1 comment Share Follow See 1 comment See all 1 1 comment reply akhil319 commented Mar 24, 2016 reply Follow Share can u share the link, where it was solved previously. 0 votes 0 votes Please log in or register to add a comment.