350 views
complement of CFL can never be CFL.

please explain if the above statement is true of false?

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.

Thanx

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.

False

False:

Compliment of CFL may or maynot be CFL.

Yes.

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?
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.
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.

Can you give an example NCFL which is not DCFL but its complement is NCFL?

https://gateoverflow.in/203733/complement-of-cfl

If this is right, then NCFL complement can be NCFL in some cases

@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.

@BHOJARAM

by