<p>Hopcroft &amp; Ullman 1979, <em>Intro to Automata Theory, Languages, &amp; Computation</em> states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are not CSLs are ultimately based on diagonalization." They give for example the universal Turing machine. I presume this statement is still true today more than three decades later but wonder anyway. </p>

<p><strong>Are there any non-CSLs known that are not "ultimately based on diagonalization"?</strong></p>

<p>I agree that this question is not necessarily strictly defined. I would also be willing to accept examples in the form where an algorithm was initially/originally built or constructed for some purpose and had unknown complexity and later the algorithm was proved to be non-CSL.</p>

<hr>

<p>Note non CSLs are also the Exp-space hard problems. <a href="http://en.wikipedia.org/wiki/Context-sensitive_language" rel="nofollow">Wikipedia mentions</a> without reference "An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation."  I would like to know a reference for this if anyone has it.</p>

CC BY-SA 3.0
2012-04-28T17:13:59.923Z
For the question in the note in the last paragraph, check the fact that all context-sensitive languages are in PSPACE.  The claim follows by combining it with the space hierarchy theorem.
Tsuyoshi Ito
CC BY-SA 3.0
2013-07-23T21:29:00.067Z
If you agree that proving uncomputability of the Busy Beaver function (http://en.wikipedia.org/wiki/Busy_beaver) does not ultimately base on diagonalization, then one can prove undecidability of the HALTING problem without diagonalization. The HALTING problem is non-CSL.
David G
<reference-request><fl.formal-languages><automata-theory><big-picture>
Examples of non-CSLs not created through diagonalization
vzn
# Examples of non-CSLs not created through diagonalization

(Asked by: username_0 on 2012-04-28)

Hopcroft & Ullman 1979, *Intro to Automata Theory, Languages, & Computation* states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are not CSLs are ultimately based on diagonalization." They give for example the universal Turing machine. I presume this statement is still true today more than three decades later but wonder anyway.

**Are there any non-CSLs known that are not "ultimately based on diagonalization"?**

I agree that this question is not necessarily strictly defined. I would also be willing to accept examples in the form where an algorithm was initially/originally built or constructed for some purpose and had unknown complexity and later the algorithm was proved to be non-CSL.

---

Note non CSLs are also the Exp-space hard problems. [Wikipedia mentions](http://en.wikipedia.org/wiki/Context-sensitive_language) without reference "An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation." I would like to know a reference for this if anyone has it.

**Tags:** reference-request, fl.formal-languages, automata-theory, big-picture

> **Comments:**
> **username_1**: For the question in the note in the last paragraph, check the fact that all context-sensitive languages are in PSPACE.  The claim follows by combining it with the space hierarchy theorem.  
> **username_2**: If you agree that proving uncomputability of the Busy Beaver function (http://en.wikipedia.org/wiki/Busy_beaver) does not ultimately base on diagonalization, then one can prove undecidability of the HALTING problem without diagonalization. The HALTING problem is non-CSL.  

---

## 0 answers

