Computationally the contextsensitive lanugages are equivalent with linear bounded nondeterministic Turing machines. That is a nondeterministic 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 contextsensitive language, and every contextsensitive language can be decided by such a machine.
This set of languages is also known as NLINSPACE, because they can be accepted using linear space on a nondeterministic Turing machine. The class LINSPACE is defined the same, except using a deterministic Turing machine. Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE=NLINSPACE. It is widely suspected they are not equal.
Every contextfree language is contextsensitive.
An example of a contextsensitive language that is not contextfree is L = { a^{n} : n is a prime number }. The easiest way to show this is using a linear bounded Turing machine.
Search Encyclopedia

Featured Article
