Figure 7.6: Dividing the string w so it can be pumped

2. Our adversary gets to pick n, which we do not know, and we therefore must plan for any possible n.

3. We get to pick z, and may use n as a parameter when we do so.

4. Our adversary gets to break z into uvwxy, subject only to the constraints that \ьюх\ < n and vx ф e.

5. We win the game, if we can, by picking i and showing that uvwxy is not in L.

We shall now see some examples of languages that we can prove, using the pumping lemma, not to be context-free. Onr first example shows that, while context-free languages can match two groups of symbols for equality or inequality, they cannot match three such groups.

Example 7.19: Let L be the language {0 1 2 n > 1). That is, L consists of all struigs in 0+1+2 with an equal number of each symbol, e.g., 012, 001122, and so on. Suppose L were context-free. Then there is an integer n given to us by the pumping lemma. Let us pick 2 = 0 1 2 .

Suppose the adversary breaks z as z = uvwxy, where \vwx\ < n and v and X are not both e. Then we know that vwx cannot involve both Os and 2s, since the last 0 and the first 2 are separated by n + 1 positions. We shall prove that L contains some string known not to be in L, thus contradicting the assumption that L is a CFL. The cases are as follows:

Remember that this n is the constant provided by the pumping lemma, and it has nothing to do with the local variable n used in the definition of L itself.

Figure 7,7: Pumping strings v and x zero times and pumping them twice

1. vwx has no 2s. Then vx consists of only Os and Is, and has at least one of these symbols. Then uwy, which would have to be in L by the pumping lenuna, has n 2s, but has fewer than n Os or fewer than n Is, or both. It therefore does not belong in L, and we conclude L is not a CFL in this case.

2, vwx has no Os. Similarly, uwy has n Os, but fewer Is or fewer 2s. It therefore is not in L.

Whichever case holds, we conclude that L has a string we know not to be in L. This contradiction allows us to conclude that our assumption was wrong; L is not a CFL. □

Another thing that CFLs cannot do is match two pairs of equal numbers of symbols, provided that the pairs interleave. The idea is made precise in the following example of a proof of non-context-freeness using the pumping lemma.

Example 7.20: Let L be the language {0П23 i > 1 and j > 1}. If L is context-free, let n be the constant for L, and pick z - 0 12 3 . We may write z = uvwxy subject to the usual constraints \vivx\ < n and vx ф e. Then vwx is either contained in the substring of one symbol, or it straddles two adjacent symbols.

Yivwx consists of only one symbol, then uwy has n of three different symbols and fewer than n of the fourth symbol. Thus, it cannot be in L. If ишж straddles two symbols, say the Is and 2s, then uwy is missing either some Is or some 2s, or both. Suppose it is missing Is. As there are n 3s, this string cannot be in L. Similarly, if it is missing 2s, then as it has n Os, uwy cannot be in L. We have contradicted the assumption that L is a CFL and conclude that it is not. □

As a final example, we shall show that CFLs cannot match two strings of arbitrary length, if the strings are chosen from an alphabet of more than one symbol. An implication of this observation, incidentally, is that grammars are not a suitable mechanism for enforcing certain semantic constraints in programming languages, such as the common requirement that an identifier be declared before use. In practice, another mechanism, such as a symbol table is used to record declared identifiers, and we do not try to design a parser that, by itself, checks for definition prior to use.

Example 7.21: Let L - \ww w is in {0,1}*}. That is, L consists of repeating strings, such as e, 0101, 00100010, or 110110. If L is context-free, then let n be its pumping-lemma constant. Consider the string z = 0 1 0 1 . This string is 01 repeated, so z is in L.

Following the pattern of the previous examples, we can break z - uvwxy, such that \vwx\ < n and vx фс. We shall show that uwy is not in L, and thus show L not to be a context-free language, by contradiction.

First, observe that, since грша; < n, \uwy\ > 3n. Thus, if uwy is some repeating string, say tt, then t is of length at least 3n/2. There are several cases to consider, depending where vwx is within z.

1, Suppose vwx is within the first n Os. In particular, let vx consist of к Os, where A; > 0. Then uwy begins with 0~*1 . Since \uwy\ = in - k, we know that if uwy - tt, then \t\ = 2n-k/2. Thus, t does not end until after the first block of Is; i.e., t ends in 0. But uwy ends in 1, and so it cannot equal tt.

2. Suppose vwx straddles the first block of Os and the first block of Is. It may be that vx consists only of Os, if i = e. Then, the argument that uwy is not of the form tt is the same as case (1). If vx has at least one