# Context-sensitive language

In theoretical computer science, a **context-sensitive language** is a formal language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). That is one of the four types of grammars in the Chomsky hierarchy.

## Computational properties

Computationally, a context-sensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. 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 **NLINSPACE** or **NSPACE**(*O*(*n*)), because they can be accepted using linear space on a non-deterministic Turing machine.^{[1]} The class **LINSPACE** (or **DSPACE**(*O*(*n*))) 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**.^{[2]}

## Examples

One of the simplest context-sensitive, but not context-free languages is : the language of all strings consisting of *n* occurrences of the symbol "a", then *n* "b"'s, then *n* "c"'s (abc, aabbcc, aaabbbccc, etc.). A superset of this language, called the Bach language,^{[3]} is defined as the set of all strings where "a", "b" and "c" (or any other set of three symbols) occurs equally often (aabccb, baabcaccb, etc.) and is also context-sensitive.^{[4]}^{[5]}

Another example of a context-sensitive language that is not context-free is *L* = { *a ^{p}* :

*p*is a prime number }.

*L*can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts

*L*. The language can easily be shown to be neither regular nor context free by applying the respective pumping lemmas for each of the language classes to

*L*.

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.

## Properties of context-sensitive languages

- The union, intersection, concatenation and Kleene star of two context-sensitive languages is context-sensitive.
^{[6]} - The complement of a context-sensitive language is itself context-sensitive
^{[7]}a result known as the Immerman–Szelepcsényi theorem. - Every context-free language not containing the empty string is context-sensitive.
^{[8]} - Membership of a string in a language defined by an arbitrary context-sensitive grammar, or by an arbitrary deterministic context-sensitive grammar, is a PSPACE-complete problem.

## See also

- Linear bounded automaton
- Chomsky hierarchy
- Indexed languages – a strict subset of the context-sensitive languages
- Weir hierarchy

## References

- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=conference }}
- ↑ Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars".
*NELS*, vol. 11, pp. 1–12. - ↑ Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors).
*Foundational Issues in Natural Language Processing*. Cambridge MA: Bradford. - ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.
- ↑ Template:Cite doi
- ↑ (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228

- Sipser, M. (1996),
*Introduction to the Theory of Computation*, PWS Publishing Co.