Context-Sensitive Grammars and Languages

A context-sensitive language is a language generated by a context-sensitive grammar.

There are two different definitions for "context-sensitive grammar," yielding grammars whose productions look quite different. However, the grammars are equivalent, in that they describe (almost) the same languages.

(Original definition) A context-sensitive grammar is one whose productions are all of the form

xAy xvy

where A V and x, v, y (V T)*.

The name "context-sensitive" comes from the fact that the actual string modification is given by Av, while the x and y provide the context in which the rule may be applied.

(Extra crispy definition) A context-sensitive grammar is one whose productions are all of the form

x y

where x, y (V T)+, and |x| |y|.

Such a grammar is called noncontracting because derivation steps never decrease the length of the sentential form.

Most modern textbooks use the second definition given above. It can be shown that the two kinds of grammars are almost equivalent (generate the same languages) with one exception: one kind of grammar permits languages to contain the empty string, while the other doesn't. (Easy question: which one permits ?)

A language L is context-sensitive if there exists a context-sensitive grammar G such that either L = L(G) or L = L(G) {}.

Notice how this definition carefully sidesteps the question of which kind of context-sensitive grammar is meant.