3 votes 3 votes complement of CFL can never be CFL. please explain if the above statement is true of false? Theory of Computation theory-of-computation context-free-language normal self-doubt + – BHOJARAM asked Dec 13, 2021 BHOJARAM 831 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Vishal_kumar98 commented Dec 13, 2021 reply Follow Share Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages. 3 votes 3 votes BHOJARAM commented Dec 14, 2021 reply Follow Share Thanx@Vishal_kumar98... so can I say that if a language is CFL but not regular then it's complement is not CFL as CFL is not closed under complement. 0 votes 0 votes raja11sep commented Nov 24, 2022 reply Follow Share False 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes False: Compliment of CFL may or maynot be CFL. Alekhyo Banerjee answered Dec 13, 2021 Alekhyo Banerjee comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments palashbehra5 commented Dec 26, 2021 reply Follow Share LRU Yes. 0 votes 0 votes LRU commented Dec 27, 2021 reply Follow Share It is an even length palindrome which is accepted by NPDA and not by DPDA, which makes it CFL rather than being DCFL. So, how it is closed under complementation? 0 votes 0 votes palashbehra5 commented Dec 27, 2021 reply Follow Share if I have got your question correct, closure properties apply to a class of languages, not to a specific language. When we say regular languages are closed under complementation, we mean any language from the whole class will still belong to that class, after the operation/combination. However, in this case, the language’s complement is CFL as well. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes If the given CFL is a DCFL then complementation is closed. But if it is an NCFL which is not a DCFL then it may or may not be closed. Sunnidhya Roy answered Nov 23, 2022 Sunnidhya Roy comment Share Follow See all 3 Comments See all 3 3 Comments reply gatecse commented Nov 23, 2022 reply Follow Share Can you give an example NCFL which is not DCFL but its complement is NCFL? 0 votes 0 votes Souvik33 commented Nov 23, 2022 reply Follow Share https://gateoverflow.in/203733/complement-of-cfl If this is right, then NCFL complement can be NCFL in some cases 1 votes 1 votes Sunnidhya Roy commented Nov 23, 2022 reply Follow Share @gatecse I am not able to formulate any such example so I am not sure whether Complement of NCFL which is not a DCFL can also be NCFL, If I consider the standard NCFL’s like ww^r || a^i b^j c^k, i>=j or j<=k complement of them are always non NCFL. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes @BHOJARAM If the above statement is : False ... CFLs are not closed under complement If L1 is a CFL, then L1 may not be a CFL…. They are closed under union. If they are closed under complement, then they are closed under intersection, which is false... 1. https://gateoverflow.in/203733/Complement-of-cfl 2. https://gateoverflow.in/6370/General-doubt aaa 1 answered Dec 26, 2021 aaa 1 comment Share Follow See all 0 reply Please log in or register to add a comment.