Now, we discover why, several weeks ago, when we discussed the pumping lemma, I wrote "pumping lemma for regular languages". Yes, it is because we are going to be talking about the pumping lemma for context-free languages today and have our first taste of the world beyond context-free languages.
Lemma (Pumping lemma for context-free languages). Let $L \subseteq \Sigma^*$ be a context-free language. Then there exists a positive integer $n$ such that for every word $w \in L$ with $|w| \geq n$, there exists a factorization $w = uvxyz$ with $u,v,x,y,z \in \Sigma^*$ such that
- $vy \neq \varepsilon$,
- $|vxy| \leq n$,
- $uv^i xy^i z \in L$ for all $i \in \mathbb N$.
This pumping lemma is due to Bar-Hillel, Perles, and Shamir in 1961. As it turns out, there are a lot of language classes for which there are pumping lemmas (deterministic context-free languages, indexed languages, regular tree languages).
The reasoning behind the pumping lemma for context-free languages is in the same vein as the one for regular languages. Since the description of any context-free grammar is finite, for a sufficiently long word, some aspect of its derivation must be repeated. For regular languages, this is analogous to the fact that a state will show up more than once on a path in a DFA. For context-free languages, this will be the fact that a variable appears more than once on a path in a parse tree.
Proof. Since $L$ is context-free, there must be a CFG $G$ in Chomsky normal form that generates it. Let $m$ be the number of variables in $G$. Then the pumping length for $L$ will be $n = 2^m$.
Consider a word $w \in L$ with $|w| \geq n = 2^m$. Since $G$ is in CNF, every parse tree for $w$ has exactly $2|w| - 1$ internal nodes and $|w|$ leaf nodes. We can choose any one of these parse trees, so let $T$ be the parse tree that we choose and fix it.
Note that $T$ has at least $2^m$ internal nodes, since $2|w| - 1 = 2 \cdot 2^m - 1 \geq 2^m$. Then there must be a path in $T$ from the root to a leaf with at least $m+1$ internal nodes. Otherwise, there could only be at most $2^m - 1$ internal nodes.
Pick a longest such path. Since there are at least $m+1$ internal nodes along this path and only $m$ variables, there must be a variable that appears twice in the path. Suppose this variable is $X$ and we have that there must be an occurrence of $X$ that is closest to the leaf on our chosen path.
Let $T_1$ and $T_2$ be two subtrees of $T$ that are rooted at the two occurrences of $X$ on the path closest to the leaf. Let $T_2$ be the tree rooted at the closest occurrence of $X$ so $T_2$ must be a proper subtree of $T_1$. Furthermore, every path from the root of $T_1$ to a leaf has at most $m+1$ internal nodes and therefore $T_1$ has at most $2^m = n$ leaf nodes.
Let $x$ be the word for which $T_2$ is the parse tree rooted at $X$ and let $v$ and $y$ be the words formed by the leaves of the parse tree $T_1$ rooted at $X$ around $T_2$ such that $T_1$ is a parse tree for the word $vxy$. Then we let $u$ and $z$ be the words formed by the leaves of $T$ around $T_1$ such that $T$ is a parse tree for the word $w = uvxyz$.
Now we need to show that $uvxyz$ is a factorization for $w$ such that the conditions of the pumping lemma hold. First, to see that $|vxy| \leq n$, we just observe that $T_1$ can have at most $2^m = n$ leaf nodes.
Next, to see that $vy \neq \varepsilon$, we note that since both $T_1$ and $T_2$ are rooted at $X$, we can construct a parse tree in which $T_1$ is removed and replaced by $T_2$. This would then be a parse tree for $uxz$. However, recall that every parse tree for a word in a grammar in CNF must have exactly the same size. Since $T_2$ was already shown to be smaller than $T_1$ we must have that $uxz \neq uvxyz$ and therefore $vy \neq \varepsilon$.
Finally, to see that $uv^ixy^iz \in L$ for all $i \in \mathbb N$, we first note that we have already shown $uv^0 xy^0 z \in L$ above. To see that this holds for $i > 1$, we can perform a similar substitution by replacing $T_2$ with $T_1$ to give us a parse tree for $uv^2xy^2$. We can then repeat this process any number of times to obtain a parse tree for $uv^ixy^iz$. $$\tag*{$\Box$}$$
Our strategy is very similar to the one we employed for regular languages. We assume that our language is context-free, then show that we are able to find a string that is unable to satisfy the conditions of the pumping lemma. However, there are a few more things to be mindful of when carrying out these proofs for context-free languages.
Proposition. Let $L = \{a^m b^m c^m \mid m \geq 0\}$. Then $L$ is not context-free.
Proof. Suppose that $L$ is context-free and let $n$ be the pumping length for $L$. Let $w = a^n b^n c^n$. Clearly, $w \in L$ and $|w| = 3n \geq n$. Now, we must consider all factorizations of $w = uvxyz$ such that $|vxy| \leq n$ and $vy \neq \varepsilon$. There are two cases to consider.
Thus, every factorization of $w = uvxyz$ fails to satisfy the pumping lemma and therefore $L$ is not context-free as assumed. $$\tag*{$\Box$}$$
The main difference between proofs using the pumping lemma for CFLs and the pumping lemma for regular languages is there is much more we have to do to ensure that we've considered all possible decompositions. The other difference is that the factorization into five factors rather than just three makes explicitly defining the factors much more of a hassle. Indeed, even in defining the cases, if we wanted to be more specific, we would have to list five different cases. Luckily, each of these cases folds nicely into just two. All of this makes choosing the word $w$ to be pumped much more important in avoiding a lot of work.
Proposition. Let $L = \{ww \mid w \in \{a,b\}^* \}$. Then $L$ is not context-free.
Proof. Suppose $L$ is context-free and let $n$ be the pumping length for $L$. Let $w = a^n b^n a^n b^n$. Then $w = (a^n b^n)^2 \in L$ and $|w| = 4n \geq n$. Now, we must consider factorizations $w = uvxyz$ with $|vxy| \leq n$ and $vy \neq \varepsilon$. There are two cases.
Thus, every factorization of $w = uvxyz$ fails to satisfy the pumping lemma and therefore $L$ is not context-free as assumed. $$\tag*{$\Box$}$$
Again, note that in the previous proof, if we were to write out each case exhaustively, we would end up with as many as seven cases to consider. Part of understanding how to go about these proofs will be understanding the process well enough to identify all of the different cases and understanding which ones can be grouped together.
Proposition. Let $L = \{ a^p \mid \text{$p$ is a prime number} \}$. Then $L$ is not context-free.
Proof. Suppose $L$ is context-free and let $n$ be the pumping length for $L$. Since there are infinitely many prime numbers, for any choice of $n$, we can always choose $p$ such that $p > n$. Let $w = a^p$ with $p \geq n$. We consider a factorization $w = uvxyz$ where $|vxy| \leq n$ and $vy \neq \varepsilon$.
Now consider for $i \in \mathbb N$ the word $uv^i x y^iz$. We can write $uv^ixy^iz = a^{p+(i-1)\cdot k}$ for $|vy| = k \leq n$ since $w$ is unary. Observe that choosing $i = p+1$ gives us $p+p\cdot k = (k+1)p$, which is not a prime number. Thus, $uv^ixy^iz \not \in P$ for $i = p+1$ and $w$ fails to satisfy the pumping lemma. Thus, $L$ is not context-free as assumed. $$\tag*{$\Box$}$$
For this problem, life is a lot simpler since being a unary language means that where the factors lie in the word is not quite as important. In fact, this proof is almost the same as the one for regular languages. A similar question was asked on the last assignment, for the set of unary words with length that differ from that of a perfect square. There is one hiccup to deal with in that case: while it's easy to see that the language of unary perfect square words is not context-free by applying the same pumping argument, it's not as obvious that its complement is also not context-free, as we haven't yet proven whether the class of CFLs is closed under complement.