Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).

Is there any language with such restrictions that isn't a Context-Sensitive language?

share|cite|improve this question
As UL is the same as recursively enumerable and CSL the same as NSPACE[n] (see, e.g., Wikipedia), you may use your favorite version of the Space hierarchy theorem to get your language in UL \ CSL. – Michaël Cadilhac Feb 22 '11 at 3:15
@Michaël Cadilhac, I think you can post it as answer so the question becomes answered. – Kaveh Feb 22 '11 at 4:26
@Kaveh You're right. @Michaël, post it as an answer, and add something if you want, to mark is at the right answer ;) – Oscar Mederos Feb 22 '11 at 4:35
Michaël Cadilhac has posted his answer, now you can accept it. – Kaveh Feb 23 '11 at 6:51
up vote 6 down vote accepted

Type 0 grammars denote exactly recursively enumerable languages, and CSL = NSPACE[$n$] (e.g., Wikipedia). Thus, your favorite proof of the Space Hierarchy Theorem gives an explicit language in, say, NSPACE[$n^2$] \ NSPACE[$n$], thus in UL \ CSL.

share|cite|improve this answer
Or more simply, any RE-complete problem, like the halting language. – Mark Reitblatt Feb 22 '11 at 14:08
Of course ; that's indeed the "farthest" language from CSL to fit, and I proposed the "farthest" language from UL for the same job. – Michaël Cadilhac Feb 22 '11 at 15:16
to be more adequate with the statement "NSPACE[n2] \ NSPACE[n], thus in UL \ CSL", better to say it is so if P<>NP. – Charles Yu Apr 18 '13 at 16:48

Since deciding membership for a context-sensitive grammar is in $PSPACE$ ($NSPACE[n]$ even), any language not in $PSPACE$ is not expressable by a context-sensitive grammar. An example is therefore the language of all true propositions in Presburger arithmetic (

Since we suspect that $PSPACE \neq EXPTIME$, we expect any $EXPTIME$-hard language to be sufficient. Alternatively, any $EXPSPACE$-hard problem is provably not context-sensitive by the space hierarchy theorem.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.