Context free language

Question

Why the complement of a CFL is CSL?

Comments

CFL’s are strict subset of CSL and CSL’s are closed under complementation so CFL complement are CSL.

Answer 1

Since CFL is not closed under complement so we can just push it above (promote it) to be a CSL. This is because Context sensitive languages (CSL) are closed under union, intersection, complement, concatenation, kleene star, reversal. Now, CSL in turn is a subset of recursive languages. Hence CFL complement is also REC.

Comments

Just to add complement of a CFL can also be regular but this is not true for EVERY CFL.