Register

ISRO2017-11

5,972 views
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?

  1. Only S1 is correct
  2. Only S2 is correct
  3. Both S1 and S2 are not correct
  4. Both S1 and S2 are correct
User Avatar

3 Answers

Best answer
9 votes
9 votes

Both are correct since context sensitive is a proper subset of recursive languages.

• edited by
User Avatar
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.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
2 answers
1
sh!va asked May 7, 2017
6,857 views
ISRO2017-77
If $L$ and $P$ are two recursively enumerable languages then they are not closed under Kleene star $L^*$ of $L$ Intersection $L \cap P$ Union $L \cup P$ Set difference
If $L$ and $P$ are two recursively enumerable languages then they are not closed underKleene star $L^*$ of $L$Intersection $L \cap P$Union $L \cup P$Set difference
User Avatar
10 votes
10 votes
8 answers
4
Arjun asked May 9, 2017
13,229 views
ISRO2017-17
Which of the following data structure is useful in traversing a given graph by breadth first search? Stack Queue List None of the above
Which of the following data structure is useful in traversing a given graph by breadth first search?StackQueueListNone of the above
User Avatar
Link Copied!