contextsensitive language
A contextsensitive language is a language^{} over some alphabet generated by generated by some known as a contextsensitive grammar.
Formally, a contextsensitive language is a formal grammar $G=(\mathrm{\Sigma},N,P,\sigma )$, such that given any production in $P$, it

1.
either has the form
$$uXv\to uwv,$$ where $X\in N$, $u,v,w\in {\mathrm{\Sigma}}^{*}$, and $w\ne \lambda $, the empty word^{},

2.
or is $\sigma \to \lambda $, provided that the start symbol $\sigma $ does not occur on the right side of any productions in $P$.
In other words, if $G$ does not contain the production $\sigma \to \lambda $, then any production will have the form in condition 1. On the other hand, if $G$ does contain $\sigma \to \lambda $, then for any production $uXv\to uwv$ of $G$, $\sigma $ does not occur in $uwv$.
The reason for including the second condition is to ensure the possibility that $\lambda $ may be generated by the grammar.
One may interpret the first condition as follows: the nonterminal symbol $X$ can only be transformed into the word $w$ if it is surrounded by $u$ and $v$, or that it is in the “context” of $uXv$. If in each production $uXv\to uwv$ of $G$, $u=v=\lambda $, (so that $X$ no longer has a “context”), then $G$ is a contextfree grammar.
Given a contextsensitive grammar $G$, the contextsensitive language generated by $G$ is $L(G)$. In other words,
$$L(G):=\{v\in {T}^{*}\mid \sigma \stackrel{*}{\to}v\},$$ 
where $T=\mathrm{\Sigma}N$ is the set of terminals, and $\sigma \stackrel{*}{\to}v$ means that the word $v$ over $\mathrm{\Sigma}$ is produced after a finite number of applications of the productions in $P$ to $\sigma $.
With condition 2, we see that a contextsensitive language contains $\lambda $ iff it is generated by a contextsensitive grammar containing $\sigma \to \lambda $. With condition 2, every contextfree language is contextsensitive. Without condition 2, every $\lambda $free contextfree language is $\lambda $free contextsensitive.
$\{{a}^{n}{b}^{n}{c}^{n}\mid n\ge 0\}$ and $\{{a}^{{2}^{n}}\mid n\ge 0\}$ are examples of contextsensitive languages that are not contextfree, the second of which is $\lambda $free.
Remarks.

1.
A formal grammar $G$ is said to be lengthincreasing if for every production $U\to V$ of $G$, the length of $U$ is at most the length of $V$: $U\le V$. Every contextsensitive grammar not containing $\sigma \to \lambda $ (condition 2) is lengthincreasing. Conversely, any language generated by a lengthincreasing grammar is contextsensitive.

2.
The minimal automaton required for processing a contextsensitive languages is a bounded nondeterministic Turing machine (bounded linear automaton).

3.
The family of contextsensitive languages has the following closure properties: union, intersection^{}, concatenation^{}, Kleene star, reversal, and complementation (proved in 1988). It is not closed under homomorphism^{}.

4.
In the Chomsky hierarchy, contextsensitive grammars are at Level 1. In fact, every contextsensitive language is recursive. The converse is not true, however.

5.
Given a contextsensitive language $L$ and a word $w$, it is decidable whether $w\in L$.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation^{} to Automata, AddisonWesley, (1969).
Title  contextsensitive language 
Canonical name  ContextsensitiveLanguage 
Date of creation  20130322 16:28:40 
Last modified on  20130322 16:28:40 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  23 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 68Q45 
Synonym  type1 language 
Synonym  type1 grammar 
Related topic  ContextFreeLanguage 
Related topic  LinearBoundedAutomaton 
Defines  contextsensitive grammar 
Defines  contextsensitive 
Defines  lengthincreasing 