Given the following statements: S1 : Every context-sensitive language L is…
2017
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?
- A.
Only S1 is correct
- B.
Only S2 is correct
- C.
Both S1 and S2 are not correct
- D.
Both S1 and S2 are correct
Attempted by 38 students.
Show answer & explanation
Correct answer: D
Statement S1 is true because every context-sensitive language can be decided by a Linear Bounded Automaton (LBA). Since LBAs operate within bounded space, they always halt on any input, making the language recursive.
Statement S2 is true because the hierarchy of formal languages is strict. There are recursive languages that require more computational resources than context-sensitive languages allow, meaning not all recursive languages are context-sensitive.
Therefore, both statements accurately describe the relationship between these language classes.