0 votes 0 votes Let L ={wxw^R / w € (a+b)* , x€(a+b)} . The complement of language L is_______ (a) Regular (b) DCFL but not regular (c) CFL but not DCFL (d) None of these Theory of Computation general + – ROHIT SHARMA 5 asked Jul 28, 2018 ROHIT SHARMA 5 1.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Since, the given language is a CFL and complement of CFL is CSL . so answer is D arvin answered Jul 29, 2018 arvin comment Share Follow See all 7 Comments See all 7 7 Comments reply ROHIT SHARMA 5 commented Jul 29, 2018 reply Follow Share Answer Given is C 0 votes 0 votes ROHIT SHARMA 5 commented Jul 29, 2018 reply Follow Share According to me...Given language is Odd Palindrone...so if u take the Complement of Given language it contains all the remaining language other than Odd Palindrone...All Even palindrone UNION Hash palindrome UNION Regular...so Complement language give CFL 0 votes 0 votes arvin commented Jul 29, 2018 reply Follow Share i think its a d for me. 0 votes 0 votes abhishekmehta4u commented Jul 29, 2018 reply Follow Share @Arvin CFL is not close under complement.means its complement may or may not be CFL. SO HOW can you sure that given language complement is not cfl???? 2 votes 2 votes arvin commented Jul 29, 2018 reply Follow Share its because we have no surity for the language to be cfl or not. but we can easily say its csl because csl is closed under complement as cfl is a strict subset of csl. 0 votes 0 votes abhishekmehta4u commented Jul 29, 2018 reply Follow Share If option are given like Cfl but not dcfl Csl but not CFL. Then what to do???? 2 votes 2 votes arvin commented Jul 29, 2018 reply Follow Share here the language L is an odd palindrome with two symbols. so its a cfl and not dcfl. because we cannot fix the centre here. on complementing we are not sure that we will get a cfl only. so its csl. answer 2 in this case. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It should be D) either it will be csl or recursive Prince Sindhiya answered Jul 29, 2018 Prince Sindhiya comment Share Follow See all 3 Comments See all 3 3 Comments reply Nitesh Choudhary commented Jul 29, 2018 reply Follow Share ans is C option is correct . because closure property satisfy mean it always hold. if not satisfy than depend on the particular case. for this question we know that language is CFL means PDA possible. than we can also make PDA for complement of this language same asa the Language but do some modification at tha final stage . so complement of this language is CFL.(don't use closure property first go by own way like try to make PDA) 0 votes 0 votes BASANT KUMAR commented Jul 29, 2018 reply Follow Share i think DCFL is closed under complement but NDCFL is not.above example is NDCFL.can you show your pda for above example 0 votes 0 votes arvin commented Jul 30, 2018 reply Follow Share How can we say that pda for the complement of the language is a PDA. i think its ambiguous to say that it will be a PDA because it will have 1)wxw 2)ww 3)wwR and i dont think we can make a pda that will satisfy the three property.. 0 votes 0 votes Please log in or register to add a comment.