5
$\begingroup$

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation, do you have to "throw out" the lemma so to speak? I am under the impression that the answer is yes, but I'm just not sure.

$\endgroup$
  • $\begingroup$ You seem to have answered your own question, so what remains? You may be interested in our reference questions. $\endgroup$ – Raphael Dec 10 '15 at 9:22
  • 3
    $\begingroup$ "you come across a case that remains true despite pumping it" -- what exactly do you mean by that? Not all words may work even if PL can be used, so you should not give up too soon. There certainly are languages that fulfill the conditions of the Pumping lemma despite not being in the resp. class. $\endgroup$ – Raphael Dec 10 '15 at 9:23
7
$\begingroup$

If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors.

Logic

The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:

$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$

This is all we know. Notice that this implication is in one direction. In other words we can't conclude:

$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$

It is a common mistake to invert the propositions in the first implication and expect to obtain a logically equivalent statement (you can't use the second statement!).

When we use the pumping lemma we are actually using the contrapositive of the first implication:

$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$

The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.

Inside the pumping lemma

Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:

Pumping lemma: If $L$ is regular then there exists a constant $N\in \mathbb{N}$ such that for all $\sigma$ in $L$ with $|\sigma|\geq N$ there exists a decomposition $\sigma=\alpha\beta\gamma$ such that:

a) $|\alpha\beta|\leq N$

b) $\beta \neq \epsilon$

c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}_0$

Common mistakes

1) My word $\sigma$ complies with the pumping lemma so $L$ must be regular:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that all $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!

2) If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!:
This is wrong too. The lemma states that there exists a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.

3) If I choose the word $\sigma=\epsilon$ I find a contradiction!:
This is wrong for two reasons. First, $N>0$. Second, the lemma states that there exists a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.

4) I tried a lot of words and all of them comply with the pumping lemma... what do I do?:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.

These are all the tips I have for now. If I can remember some more in the future I will add them here.

$\endgroup$
4
$\begingroup$

This question refers to "the pumping lemma" but there are actually several pumping lemmas available. Thus a short answer to the question "Do you have to "throw out" the lemma?" might be "Try a stronger version first".

1. Regular languages.

Let us first state the standard pumping lemma.

Pumping lemma. If $L$ is regular, then there exists $k > 0$ such that each word $y$ of length $\geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $n \geqslant 0$, $$ uv^nw \in L \iff uvw \in L $$ If the pumping lemma fails, you can try its contextual version. According to Wikipedia, the language $\{ a^mb^nc^n \mid m > 0 \text{ and } n > 0\}$ satisfies the pumping lemma, but can be proven to be non-regular by using its contextual version.

Pumping lemma (contextual version). If $L$ is regular, then there exists $k > 0$ such that, for all words $x$, $y$, $z$ with $|y| \geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $n \geqslant 0$, $$ xuv^nwz \in L \iff xuvwz \in L $$ The pumping lemma, even in its contextual version, only gives a necessary condition for a language to be regular, but there are more powerful versions giving necessary and sufficient conditions. The first one is due to Jaffe [2]

Jaffe's pumping lemma. A language $L$ is regular if and only if there exists $k > 0$ such that each word $y$ of length $\geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $z$ and for all $n \geqslant 0$ $$ uv^nwz \in L \iff uvwz \in L $$ Note the subtle difference with the contextual version of the pumping lemma: the pump is now uniform for all $z$...

Other sufficient conditions using "block pumping properties" were proposed in [1] and [3]. A language $L$ satisfies the block pumping property if there exists $m > 0$ such that, for any $x$, $u_1, u_2, \ldots ,u_m, y$, there exist $i,j$ such that $1 \leqslant i < j \leqslant m + 1$ such that, for all $n \geqslant 0$, $$ xu_1u_2 \cdots u_{i-1} (u_i \cdots u_{j−1})^n u_j \cdots u_my \in L \iff xu_1u_2 \cdots u_my \in L \quad (*) $$ A language $L$ satisfies the positive block pumping property if $(*)$ holds for all $n > 0$. Ehrenfeucht, Parikh and Rozenberg [1] proved the following result.

EPR's block pumping lemma. A language is regular if and only if it satisfies the block pumping property.

This result was improved by Varricchio [4] as follows:

Varricchio's block pumping lemma. A language is regular if and only if it satisfies the positive block pumping property.

See also [3] for other conditions.

[1] A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, SIAM J. Comput. 10 (1981), 536-541.
[2] J. Jaffe, A necessary and sufficient pumping lemma for regular languages, Sigact News - SIGACT 10 (1978) 48-49.
[3] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages (Monographs in Theoretical Computer Science. An EATCS Series), Springer 1999. ISBN: 978-3-540-63771-4 (Print) 978-3-642-59849-4 (Online) [4] S. Varricchio, A pumping condition for regular sets, SIAM J. Comput. 26 (1997) 764-771.

2. Context-free languages.

This case is thoroughly discussed in the question How to prove that a language is not context-free?. Pumping lemmas for context-free languages include the standard version of the pumping lemma and Ogden's lemma.

Raphael's nice answer also mentions the Interchange Lemma and gives further references.

Updated references.

C. Bader, A. Moura, A Generalization of Ogden’s Lemma. JACM 29, no. 2, (1982), 404-407.

R. Boonyavatana, G. Slutzki, The interchange or pump (DI)lemmas for context-free languages, TCS 56 (1988) 321-338

P. Dömösi and M. Kudlek, Strong Iteration Lemmata for Regular, Linear, Context-Free, and Linear Indexed Languages, G. Ciobanu and G. Paun (Eds.): FCT'99, LNCS 1684, pp. 226–233, (1999).

W. Ogden, R. J. Ross and K. Winklmann, An "interchange lemma" for context-free languages, SIAM J. Comput. 14 (1985) 410-415.

D.S. Wise, A strong pumping lemma for context-free languages, J. Comput. System Sci. 3 (1976) 359-370.

$\endgroup$
  • 2
    $\begingroup$ Excellent answer! Too bad they don't tell us these things when teaching us the usual pumping lemmas. $\endgroup$ – Yuval Filmus Dec 12 '15 at 22:47
  • $\begingroup$ There is also Ogden's lemma ! $\endgroup$ – GBat Jan 18 at 18:08
  • $\begingroup$ @GBat Ogden's lemma is already mentioned in my answer. $\endgroup$ – J.-E. Pin Jan 20 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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