patternModerate
Complement of CFL is Recursive
Viewed 0 times
complementcflrecursive
Problem
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 ?
My doubt arose because I think if a language cannot be decided CFL or not then how can it be declared Recursive ?
Solution
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.
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.
Context
StackExchange Computer Science Q#65798, answer score: 15
Revisions (0)
No revisions yet.