I. Whether a given string $w$ belongs to a given CSL $L$.
- 1. CSLs are Recursive: By definition, every Context-Sensitive Language (CSL) is a Recursive Language. This is a fundamental theorem of computability.
- 2. Recursive Languages Have Deciders: The very definition of a Recursive Language is that a Halting Turing Machine (a decider) exists for it.
- 3. Deciders Solve the Problem: This Halting TM is the algorithm for the membership problem. When given an input string $w$:
- If $w$ is in the language $L$, the TM is guaranteed to halt in an accept state.
- If $w$ is not in the language $L$, the TM is guaranteed to halt in a reject state.
Since a Halting TM exists for this problem, the problem is DECIDABLE.
II. Whether the language accepted by a TM is context-free.
- UNDECIDABLE. This is a non-trivial property of the language $L(M)$. Some TMs accept context-free languages (like $a^n b^n$ ), and some accept non-context-free languages (like $\left.a^n b^n c^n\right)$. By Rice's Theorem, this is undecidable.
III. Whether a given grammar $G$ qualifies as a CSG.
- DECIDABLE. This is a simple syntactic check. We just need an algorithm to iterate through all production rules $\alpha \rightarrow \beta$ and verify that $|\alpha| \leq|\beta|$. This algorithm always halts.
IV. Whether the language generated by a CSL is empty.
- UNDECIDABLE. The emptiness problem for Context-Sensitive Languages is a wellknown undecidable problem.
