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

Dark Mode

219 views

1 vote

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.