If CFL are not closed under complementation, it means that if a language '$L$' is CFL then its compliment $L^C$ is not CFL. Then how can we discuss about $L^C$ being recursive?

My doubt arose because I think if a language cannot be decided CFL or not then how can it be declared Recursive ?

  • 1
    $\begingroup$ CFL not being closed under complementation does not mean that a 'L' being in CFL means that it's complement is not in CFL. It just means that there exists an 'L' in CFL such that it's complement is not in CFL. $\endgroup$
    – Taemyr
    Commented Nov 9, 2016 at 21:08

1 Answer 1


You can think of it as " every CFL is Recursive".
And Recursive languages are closed under complementation.

Therefore, if a language $L$ is CFL then it is also recursive and hence, $L^C$ is also recursive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.