[Overview] [Previous] [Next]

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 goes to xvy

where A is a member of V and x, v, y is a member of (V union T)*.

The name "context-sensitive" comes from the fact that the actual string modification is given by Agoes tov, 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 goes to y

where x, y is a member of (V union 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 empty string?)

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

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