[Overview] [Previous] [Next]

Relationship To Other Grammars

Theorem. Every context-free language is context-sensitive.

Proof. The productions of a context-free language have the form Agoes tov. The productions of a context-sensitive language have the form xAygoes toxvy, where x and y are permitted to be empty string. Q.E.D.

 

Theorem. There exists a context-sensitive language that is not context-free.

Proof. The language {an timesbn timescn times: n >= 0} is not context-free (we used a pumping lemma to show this). We can show that it is context-sensitive by providing an appropriate context-sensitive grammar. Here are the productions for one such grammar:

S goes to aXBC S goes to aBC X goes to aXBC
X goes to aBC CB goes to BC aB goes to ab
bB goes to bb bC goes to bc cC goes to cc

 

Theorem. Every context-sensitive language is recursive.

Proof. A context-sensitive grammar is noncontracting; moreover, for any integer n there are only a finite number of sentential forms of length n. Therefore, for any string w we can set a bound on the number of derivation steps required to generate w, hence a bound on the number of possible derivations. The string w is in the language if and only if one of these derivations produces w.

 

Theorem. There exists a recursive language that is not context-sensitive.

An appropriate example language is given in the textbook.

Copyright © 1996 by David Matuszek
Last modified Apr 9, 1996