7 votes 7 votes Given the following statements S1 : Every context-sensitive language $L$ is recursive S2 : There exists a recursive language that is not context-sensitive Which statements are true? Only S1 is correct Only S2 is correct Both S1 and S2 are not correct Both S1 and S2 are correct Theory of Computation isro2017 theory-of-computation context-sensitive + – sh!va asked May 7, 2017 sh!va 6.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 9 votes 9 votes Both are correct since context sensitive is a proper subset of recursive languages. Ishan Jawa answered May 7, 2017 • edited May 10, 2017 by Prashant. Ishan Jawa comment Share Follow See all 0 reply Please log in or register to add a comment.
5 votes 5 votes option D will be correct... akash.dinkar12 answered May 7, 2017 akash.dinkar12 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Both S1 and S2 are correct. from Chomsky Hierarchy, Context Sensitive Language is subset of Recursive. Hence S1 is TRUE. A language can be Recursive but need not be CSL. Hence S2 is also TRUE. AnilGoudar answered May 7, 2017 AnilGoudar comment Share Follow See all 0 reply Please log in or register to add a comment.