Pumping lemma for CFL

Question

Q: Show that L={ww|w ∈ {0,1}*} is not context free

My solution:

Assume L is context free

Let its pumping length be P

thus,

string = 0^P 1^P 0^P 1^P

let P=2, S= 00 11 00 11

S can be divided as u v^i x y^i z

0 0 110 0 11
u v  x  y  z

after pumping,

0 00 110 00 11
u  v  x   y  z

0^3 1^2 0^3 1^2 therefore its takes the form of ww ( first condition met)

|vy|=4>0 (second condition met)

|vxy|= 7 which is greater than pumping length 2 (3rd condition is not met)

Therefore, contradicts assumption that L is context free.

Thus L is not context free

---

Is my proof correct?

Answer 1

This proof is not correct. Where it goes off the rails is here:

let P=2, S= 00 11 00 11

You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.

The next mistake is this:

S can be divided as u v^i x y^i z […]

It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.

You were definitely on the right track with this:

string = 0^P 1^P 0^P 1^P

From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.

1. v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
2. v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
3. v and y consist only of 1s from the second section of the string. Basically the same as (1)
4. v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
5. v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
6. v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
7. v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).

These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).