# Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.

Every context-sensitive language L is recursive.

Proof: Consider the context-sensitive language $$L$$ with an associated context- sensitive grammar $$G$$, and look at a derivation of $$w$$

$$S \Rightarrow x_1 \Rightarrow x_2 ... \Rightarrow x_n \Rightarrow w$$.

We can assume without any loss of generality that all sentential forms in a single derivation are different; that is, $$x_i \neq x_j$$ for all $$i\neq j$$ . The crux of our argument is that the number of steps in any derivation is a bounded function of $$|w|$$. We know that $$|x_j| \leq|x_{j + 1}|,$$

because $$G$$ is noncontracting. The only thing we need to add is that there exist some $$m$$, depending only on $$G$$ and $$w$$, such that

$$|x_j| \lt|x_{j + m}|,$$

for all $$j$$, with $$m = m(|w|)$$ a bounded function of $$|V\cup T|$$ and $$|w|$$. This follows because the finiteness of $$|V \cup T|$$ implies that there are only a finite number of strings of a given length. Therefore, the length of a derivation of $$w \in 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 \in L$$, otherwise it is not. ■

What I could reason on my own is that, since context sensitive grammars are non contracting, we can apply the productions in steps, and if we get more $$|w|$$ symbols in the right sentential form, it then when we stop. So we shall be ultimately above to check where $$w$$ is generated by a context sensitive grammar or not.

What he wants to show here is that for any sentence of some given length, there is a (very large but finite) number $$m$$ which is the maximum number of steps in a derivation of the sentence.
If that is true (which it is), then we can figure out whether or not a sentence is generated by the grammar by enumerating all possible derivations with at most $$m$$ steps. If we encounter the sentence in one of these derivations, then we have derived it. Otherwise no derivation exists.
• now I got it. When the author says that $|x_j|<|x_{j+m}|$ he means that the length of sentence might increase (due to the $<$ sign used) upto a certain number $m$ which is a finite number (possibly very large) as you have explained. Thank you. Apr 13 at 5:55