In
formal language theory, a context-sensitive grammar is defined by a
finite set of rewriting rules of the form
[X]Y[Z] -> W
where X, Z, and W are strings of symbols, and Y is a single symbol.
Such a rule means: within a string of symbols, if a substring is equal to XYZ, the Y may be replaced with W.
This can be regarded as a restricted form of general grammar, namely, one in which all rules are of the form XYZ -> XWZ. Unlike in general grammars, only one symbol can be rewritten at a time.
If all rewriting contexts are empty, we have a context-free grammar.
It can be shown that the set of languages that can be generated by context-sentitive grammars, the context-sensitive languages, is strictly greater than the context-free languages, but strictly included in the set of languages that arbitrary grammars can generate.
Furthermore, it can be shown that the non-increasing grammars, the grammars in which all rules have at least as many symbols to the left as to the right, generate exactly the context-sensitive languages. For both categories of grammars, it is possible to decide, given a grammar and a string, whether or not the grammar can generate the string.