4
$\begingroup$

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 ?

| cite | improve this question | | | | |
$\endgroup$
  • 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 Nov 9 '16 at 21:08
12
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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