<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-23T10:03:24.017Z
2011-02-23T10:03:24.017Z
Alex ten Brink
<p>Type 0 grammars denote exactly recursively enumerable languages, and CSL = NSPACE[$n$] (e.g., <a href="http://en.wikipedia.org/wiki/Chomsky_hierarchy">Wikipedia</a>).  Thus, your favorite proof of the <a href="http://en.wikipedia.org/wiki/Space_hierarchy_theorem">Space Hierarchy Theorem</a> gives an explicit language in, say, NSPACE[$n^2$] \ NSPACE[$n$], thus in UL \ CSL.</p>

CC BY-SA 2.5
2011-02-22T14:08:32.093Z
Or more simply, any RE-complete problem, like the halting language.
Mark Reitblatt
CC BY-SA 2.5
2011-02-22T15:16:41.877Z
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
CC BY-SA 3.0
2013-04-18T16:48:04.923Z
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
CC BY-SA 2.5
2011-02-22T13:50:56.383Z
2011-02-22T13:50:56.383Z
Michaël Cadilhac
<p>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 <strong>Type 0</strong> ($UL$) and not in <strong>Context-Sensitive Languages</strong> ($CSL$).</p>

<p>Is there any language with such restrictions that isn't a <strong>Context-Sensitive</strong> language?</p>

CC BY-SA 2.5
2011-02-22T03:15:28.877Z
As UL is the same as recursively enumerable and CSL the same as NSPACE[n] (see, e.g., [Wikipedia](http://en.wikipedia.org/wiki/Chomsky_hierarchy)), you may use your favorite version of the [Space hierarchy theorem](http://en.wikipedia.org/wiki/Space_hierarchy_theorem) to get your language in UL \ CSL.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-22T04:26:25.870Z
@Michaël Cadilhac, I think you can post it as answer so the question becomes answered.
Kaveh
CC BY-SA 2.5
2011-02-22T04:35:26.550Z
@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
<fl.formal-languages><grammars>
Is there an example of a non context-sensitive language?
Oscar Mederos
# Is there an example of a non context-sensitive language?

(Asked by: username_0 on 2011-02-22)

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?

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: As UL is the same as recursively enumerable and CSL the same as NSPACE[n] (see, e.g., [Wikipedia](http://en.wikipedia.org/wiki/Chomsky_hierarchy)), you may use your favorite version of the [Space hierarchy theorem](http://en.wikipedia.org/wiki/Space_hierarchy_theorem) to get your language in UL \ CSL.  
> **username_2**: @Michaël Cadilhac, I think you can post it as answer so the question becomes answered.  
> **username_0**: @Kaveh You're right. @Michaël, post it as an answer, and add something if you want, to mark is at the right answer ;)  

---

## 2 answers

### Answer by username_1 on 2011-02-22. Score: 8 | Accepted answer

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

> **Comments:**
> **username_4**: Or more simply, any RE-complete problem, like the halting language.  
> **username_1**: Of course ; that's indeed the "farthest" language from CSL to fit, and I proposed the "farthest" language from UL for the same job.  
> **username_5**: to be more adequate with the statement "NSPACE[n2] \ NSPACE[n], thus in UL \ CSL", better to say it is so if P<>NP.  

---

### Answer by username_3 on 2011-02-23. Score: 3

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.


---

