0
$\begingroup$

Related questions:

  1. Can regular languages be Turing complete?
  2. Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
  3. https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive
  4. https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is already answered by your first link, since every regular language is also context-sensitive. $\endgroup$
    – David Richerby
    Commented Jun 6, 2019 at 12:55

2 Answers 2

Reset to default
4
$\begingroup$

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct.

To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The proof is not difficult and comes from Alan Turing himself). That means that we can associate every positive integer with some Turing machine, in such a way that every machine has a unique index.

Now, take the language $L_1 = \{a^i \mid i > 0\}$ (where $a^i$ means a string consisting precisely of $i$ $a$s). Since any string of $a$s is in $L_1$, the language is equivalent to the regular expression $a^+$.

The semantics of a program in $L_1$ is simple: it does whatever Turing machine number $i$ would do, where $i$ is the length of the program. That's clearly a Turing complete regular language.

Then we define $L_2 = \{a^ib^i\mid i>0\}$ and $L_3 = \{a^ib^ic^i\mid i>0\}$, with the same semantics: in each case, program $i$ executes Turing machine number $i$. So these languages are also Turing complete, but $L_2$ is context-free and $L_3$ is context-sensitive.

Now, let's redefine the semantics. We'll define three languages with exactly the same syntaxes, but instead of executing Turing machine $i$, they print out $i$ in binary and then halt. These three new languages are still regular, context-free and context-sensitive, respectively, since the syntaxes have not changes. But none of them is Turing complete.

Bottom line: What a language means and how it is expressed are completely different concepts.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, the answer is, if a Context Sensitive language is properly written, it can be Turing Complete? Can regular languages be Turing complete? $\endgroup$
    – user
    Commented Jun 6, 2019 at 3:18
  • $\begingroup$ The answer is that syntax and semantics are totally orthogonal. The syntactic category of a language tells you absolutely nothing about its computational power, and vice versa. $\endgroup$
    – rici
    Commented Jun 6, 2019 at 6:02
-1
$\begingroup$

Any context-sensitive language is decidable and can be recognised by a Turing machine in NLINSPACE. Recognising a string from an arbitrary deterministic context-sensitive grammar is PSPACE-complete.

Moreover, just as context-free languages are equivalent to NPDAs, context-sensitive languages are equivalent to linear-bounded automata. Every CSL can be recognised by an LBA, and the language recognised by any LBA is a CSL.

All of the above is fairly standard (since it's type-1 on the Chomsky hierarchy) and covered in any decent textbook on languages and automata.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Yes, but that's not what OP is asking about. They want to know about the computational power of the language, not the difficulty of parsing it. $\endgroup$
    – rici
    Commented Jun 6, 2019 at 7:50
  • $\begingroup$ What is the "computational power" of a formal language if not the complexity class and class of automata that can recognise it? $\endgroup$
    – Pseudonym ♦
    Commented Jun 7, 2019 at 6:14

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