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 = { an : n is a prime number }. The easiest way to show this is using a linear bounded Turing machine.
Computational properties
Examples
See also: Chomsky hierarchy