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

**Proof.** The productions of a context-free language have the form Av.
The productions of a context-sensitive language have the form xAyxvy,
where x and y are permitted to be .
Q.E.D.

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

**Proof.** The language {abc:
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 aXBC S aBC X aXBC X aBC CB BC aB ab bB bb bC bc cC 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