1
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ Did you try the usual translation into competitive game between one player representing $\forall$ statements and another player representing $\exists$ statements? $\endgroup$ – Apiwat Chantawibul Sep 26 '17 at 13:57
  • $\begingroup$ I have seen the ∀ and ∃ version of the lemma but haven't heard of the competitive game. Can you tell more about it? $\endgroup$ – labl Sep 26 '17 at 14:00
  • $\begingroup$ 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. $\endgroup$ – Raphael Sep 27 '17 at 18:35
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.