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.


1 Answer 1


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.

There are a finite number of such derivations, so this process will eventually finish. That makes it recursive, since it eventually finishes both on success and on failure). (It won't finish during the lifetime of the universe but mathematicians are allowed to ignore inconvenient aspects of reality).

Type 0 grammars (not context-sensitive) are not non-contracting, so we can't limit the number of possible derivation steps. We can still enumerate all possible derivations in order by derivation length (in steps), but we have no guarantee that the process will ever terminate on failure. (More accurately, there is no point on the enumeration at which we can say that a derivation for the sentence will never appear.) So Type 0 grammars are recursively enumerable, but not recursive.

  • $\begingroup$ 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. $\endgroup$ Apr 13, 2021 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.