because G is non contracting. The only thing we need to add is that there exist
some m, depending only on G and w, such that
for all j, with m = m(|w|) a bounded function of |V ∪ T| and |w|. This follows
because the finiteness of |V ∪ T| implies that there are only a finite number of
strings of a given length. Therefore, the length of a derivation of w ∈ L is at
most |w| m(|w|).
This observation gives us immediately a membership algorithm for L. We
check all derivations of length up to |w| m(|w|). Since the set of productions of G
is finite, there are only a finite number of these. If any of them give w, then w ∈
L, otherwise it is not.
Theorem 11.11
There exists a recursive language that is not context-sensitive.
Proof: Consider the set of all context-sensitive grammars on T = {a, b}. We can
use a convention in which each grammar has a variable set of the form
Every context-sensitive grammar is completely specified by its productions; we
can think of them as written as a single string
To this string we now apply the homomorphism