Lecture 12, Oct. 30, 2001.

Done in class:

(1) Pumping Lemma for Context-Free Languages

    Examples of proofs that a language L is not CFL

When proving the language L={a^n b^n^2 | n >0} is not a CFL, I 
forgot to consider one case. I'll do it now.

Recall that our string s=a^p b^p^2, for p the pumping length given
by the Pumping Lemma for L. Let s=uvxyz be the decomposition of s 
satisfying the Pumping Lemma.

The case we haven't considered in class is when v=a^k and y=b^l, 
for k and l such that k+l <= p, and either k or l is non-zero.

Then, if the Pumping Lemma were to hold for L, we must have that both
uxz and uvvxyyz should be in L. Note that uxz has p-k symbols a, and p^2-l
symbols b; the string uvvxyyz has p+k symols a, and p^2+l symbols b. If both 
these strings are in L, it must be the case that

p^2-l = (p-k)^2 = p^2 -2pk + k^2, and
p^2+l = (p+k)^2 = p^2 +2pk + k^2.

Subtracting the first equality from the second one, we obtain:

2l = 4pk, and hence, l = 2pk.

But, we know that k+l <= p, an so, l<= p < 2pk. Thus, we get a contradiction.


(2) Turing machines: Introduction


Assigned reading: Sec. 3.1.