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.

Log in or register to write something here or to contact authors.