for all i =0, 1, 2,….
Note that the conclusions of this theorem differ from those of Theorem 8.1,
since (8.2) is replaced by (8.5). This implies that the strings v and y to be
pumped must now be located within m symbols of the left and right ends of w,
respectively. The middle string x can be of arbitrary length.
Proof: Since the language is linear there exists a linear grammar G for it. For the
argument it is convenient to assume that G has no unit-productions and no λproductions. An examination of the proofs of Theorem 6.3 and 6.4 makes it clear
that removing unit-productions and λ-productions does not destroy the linearity
of the grammar. We can therefore assume that G has the required property.
Consider now the derivation of a string ω ε L(G)
Assume, for the moment, that for every w G L(G), there is a variable A, such
that
1.in the partial derivation
no variable is repeated,
2.in the partial derivation
no variable except A is
repeated,
3.the repetition of A must occur in the first m steps, where m can depend on the
grammar, but not on ω.
If this is true, then the lengths of u, v, y, z must be bounded independent of w.
This in turn implies that (8.5), (8.6), and (8.7) must hold.
To complete the argument, we must still demonstrate that the above
conditions hold for every linear grammar. This is not hard to see if we look at
sequences in which the variables can occur. We will omit the details here, but
leave them as an exercise (see Exercise 16 at the end of this section).
Example 8.6
The language
is not linear.