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 921 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 LRU commented Dec 13, 2021 reply Follow Share Please give an example of a language which is CFL and whose complement is CFL as well, satisfying that it is not regular. 0 votes 0 votes raja11sep commented Dec 13, 2021 reply Follow Share L={a^nb^n | n>=0} → L’ = {a^mb^n | n!=m ,n>=0,m>=0} Both CFL. 0 votes 0 votes LRU commented Dec 13, 2021 reply Follow Share Brother this is DCFL and I know very well that DCFLs are closed under complementation. Please give an example of CFL which is neither DCFL nor Regular and which satisfies complementation closure property. 0 votes 0 votes raja11sep commented Dec 13, 2021 reply Follow Share I just answered as per your question. 0 votes 0 votes LRU commented Dec 13, 2021 reply Follow Share Please answer now 0 votes 0 votes raja11sep commented Dec 13, 2021 reply Follow Share L={WW^R | W belongs to {a,b}} W^R is reverse of W. 0 votes 0 votes LRU commented Dec 13, 2021 reply Follow Share L={WW^R | W belongs to {a,b}} W^R is reverse of W. Its complementation is CFL? 0 votes 0 votes 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.