Closure Properties of Languages

Question

let L = “CFL but not REGULAR”, Can we get complement of L as CFL?

Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.

Answer 1

Yes, you can get a complement of language which is cfl but not regular as CFL.

L={a^nb^n | n>=0} this is a cfl which is not regular.Now it’s complement L’ ={a^mb^n | m!=n} this is also a cfl.

CFL’s are not closed under complementation. The complement of a CFL may or may not be CFL.

Comments

The language you have pointed out is a DCFL and is indeed closed under complementation.

---

Yes.But is it violating his doubt?

---

L’ would be {a^mb^n | m!=n} U ‘ba’ as substring

Since Regular union with CFL is always CFL, L’ is also a CFL.