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$

closed as too broad by Raphael Sep 27 '17 at 18:36

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.