#selfDoubt

Question

complement of CFL can never be CFL.

please explain if the above statement is true of false?

Comments

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

---

False

Answer 1

False:

Compliment of CFL may or maynot be CFL.

Comments

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

Answer 2

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.

Comments

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.

Answer 3

@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