 Contextsensitive language

In theoretical computer science, a contextsensitive language is a formal language that can be defined by a contextsensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used, in both theory and practice.
Contents
Computational properties
Computationally, a contextsensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. 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.
Examples
An example of a contextsensitive language that is not contextfree is L = { a^{p} : p is a prime number }. L can be shown to be a contextsensitive 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 contextsensitive is any recursive language whose decision is an EXPSPACEhard problem, say, the set of pairs of equivalent regular expressions with exponentiation.
Properties of contextsensitive languages
 The union, intersection, and concatenation of two contextsensitive languages is contextsensitive.
 The complement of a contextsensitive language is itself contextsensitive.
 Every contextfree language is contextsensitive.
 Membership of a string in a language defined by an arbitrary contextsensitive grammar, or by an arbitrary deterministic contextsensitive grammar, is a PSPACEcomplete problem.
See also
 Linear bounded automaton
 Chomsky hierarchy
 Noncontracting grammars – generate exactly the contextsensitive languages
 Indexed languages – a strict subset of the contextsensitive languages
References
 Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
 Immerman, Neil (1988). "Nondeterministic space is closed under complementation". SIAM J. Comput. 17 (5): 935–938. doi:10.1137/0217058. http://www.cs.umass.edu/~immerman/pub/space.pdf.
Automata theory: formal languages and formal grammars Chomsky hierarchy Type0—Type1———Type2——Type3—Grammars (no common name)Linear contextfree rewriting systems etc.Treeadjoining etc.—Languages ContextsensitiveMinimal automaton Thread automataEach category of languages is a proper subset of the category directly above it.  Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it. Categories: Formal languages
Wikimedia Foundation. 2010.