Computationally the context-sensitive languages are equivalent with linear bounded non-deterministic Turing machines. That is a non-deterministic Turing machine with a tape of only *kn* cells, where *n* is the size of the input and *k* is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.

This set of languages is also known as **NLIN-SPACE**, because they can be accepted using linear space on a non-deterministic Turing machine. The class **LIN-SPACE** is defined the same, except using a deterministic Turing machine. Clearly **LIN-SPACE** is a subset of **NLIN-SPACE**, but it is not known whether **LIN-SPACE**=**NLIN-SPACE**. It is widely suspected they are not equal.

Every context-free language is context-sensitive.

An example of a context-sensitive language that is not context-free is *L* = { *a*^{n} : *n* is a prime number }. The easiest way to show this is using a linear bounded Turing machine.