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.
