3 votes 3 votes L = {w | no of 0's in w != no of 1's in w and w Ɛ(0+1)*} What is the Language L? a. Regular b. CFL C. CSL Theory of Computation theory-of-computation regular-language + – Arnab Bhadra asked Nov 22, 2017 Arnab Bhadra 683 views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Red_devil commented Nov 22, 2017 reply Follow Share B. CFL 0 votes 0 votes Ashwin Kulkarni commented Nov 22, 2017 reply Follow Share B. CFL (because we need to count number of 0's and then need to compare it with no. of 1's using stack) 0 votes 0 votes akash.dinkar12 commented Nov 22, 2017 reply Follow Share Its B... 0 votes 0 votes Diksha Aswal commented Nov 22, 2017 reply Follow Share B option is correct 0 votes 0 votes Shubhanshu commented Nov 22, 2017 reply Follow Share infact it is DCFL. 1 votes 1 votes just_bhavana commented Nov 22, 2017 i edited by just_bhavana Nov 22, 2017 reply Follow Share Yes, because DCFLs are closed under complementation and $\overline{L}$ is nothing but language of strings having equal number of 0's and 1's 2 votes 2 votes Hemant Parihar commented Nov 22, 2017 reply Follow Share @just_bhavana, you are correct Language will be DCFL, but $\bar{L}$ is not {$0^n$$1^n$ | n >= 0}. Here there is no specific order like all the 1's are followed by all the 0's. OR all the 0's is followed by all the 1's. 1 and 0 can occur in any order. 2 votes 2 votes Diksha Aswal commented Nov 22, 2017 reply Follow Share Yes, { 0n1n|n≥0 } it is not able to accept 010101.... or any order of 0 and 1 with equal number of 0's and 1's 1 votes 1 votes Anu007 commented Nov 22, 2017 reply Follow Share what about {1n0n | n>=1} 0 votes 0 votes Diksha Aswal commented Nov 22, 2017 reply Follow Share It means there must be atleast one string forming 10 but it still not able to from any order f 0 and 1 it will form 10,1100,111000, .. 0 votes 0 votes Anu007 commented Nov 22, 2017 reply Follow Share Diksha m not sying this is language but i was saying she miss these strings atleast since 0 and 1 are equal. 0 votes 0 votes Diksha Aswal commented Nov 22, 2017 reply Follow Share yes, right 0 votes 0 votes just_bhavana commented Nov 22, 2017 reply Follow Share yes @hemant, thanks for the correction. It will simply accept all strings over {0,1} having equal number of 0's and 1's 0 votes 0 votes Shubhanshu commented Nov 22, 2017 reply Follow Share Complement will n0 = n1. 0 votes 0 votes Please log in or register to add a comment.