Problem Detail: 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 ?
Asked By : Vidhi
Answered By : Akash Mahapatra
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65798 Ask a Question Download Related Notes/Documents
