# Tips for understanding the Pumping Lemma for Context-Free Languages [closed]

I'm having a hard time wrapping the idea in my head. Can anyone explain this as different from Sipser's perspective?

(I saw one discussion in reddit but it's for regular languages) https://www.reddit.com/r/compsci/comments/1pnjrp/the_pumping_lemma/

• Did you try the usual translation into competitive game between one player representing $\forall$ statements and another player representing $\exists$ statements? – Apiwat Chantawibul Sep 26 '17 at 13:57
• I have seen the ∀ and ∃ version of the lemma but haven't heard of the competitive game. Can you tell more about it? – labl Sep 26 '17 at 14:00
• Reproducing textbook chapters is no good for this platform. Get another book, or try to formulate a more specific question! You can also check our reference questions, and the question tagged pumping-lemma. – Raphael Sep 27 '17 at 18:35

One way of looking at the pumping lemma is in terms of the pumping game, a two-player game parametrized by an infinite language $L$. The two players are the Prover and Challenger, and the game goes as follows:

1. Prover picks an integer $n$.
2. Challenger picks a word $w \in L$ of length at least $n$.
3. Prover chooses a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \ge 1$.
4. Challenger chooses an integer $i$.
5. If $xy^iz \in L$ then Prover wins, otherwise Challenger wins.

The pumping lemma states that:

If $L$ is regular then Prover has a winning strategy.

The pumping lemma is often used in the contrapositive:

If Challenger has a winning strategy then $L$ is not regular.

Here is an example: we will show that Challenger has a winning strategy for the language $L = \{a^nb^n : n \geq 0\}$.

In response to Prover's choice of $n$, Challenger chooses the word $w = a^n b^n$. In response to Prover's choice of a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \geq 1$, Challenger chooses $i=0$. Then $xy^iz = a^{n-|y|}b^n \notin L$, and so Challenger wins.

This is simply an application of a well-known correspondence between logic and games to the statement of pumping lemma.

First notice that for any statement of the form: $$S = \exists a_1 \ldotp \forall b_1 \ldotp \exists a_2 \ldotp \forall b_2 \ldotp \ldots \exists a_n \ldotp \forall b_n \ldotp p(a_1,b_1,a_2,b_2,\ldots a_n,b_n)$$ Here, truth value of $p$ is a function of variables $a_1,b_2,\ldots,a_n,b_n$. There is a corresponding (two-player, zero-sum, extensive-form) game $G_S$ where

• $\exists$-player wins when the statement $p$ is true
• $\forall$-player wins when the statement $p$ is false
• The players take alternating turns instantiating the value of variables in order of $a_1, b_1, \ldots ,a_n,b_n$ starting with the $\exists$-player.

The statement $S$ is:

• true exactly when $\exists$-player has a winning strategy
• false exactly when $\forall$-player has a winning strategy

For the explicit application of this translation for pumping lemma, please see Yuval Filmus's answer.