# Is there an example of a non context-sensitive language?

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?

• 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

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.
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 (en.wikipedia.org/wiki/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.