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.

Copyright © 1996 by David Matuszek

Last modified Apr 9, 1996