# necessary and sufficient pumping lemma - bounded pumping variant

There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.

According to that lemma:

A language $$L$$ is regular iff $$\exists k$$, $$\forall x\in \Sigma^k$$, $$\exists u,v,w\in \Sigma^*$$, $$x=uvw \cap |v|\ge 1$$ such that:

$$\forall i \ge 0,\ \forall z\in \Sigma^*: uvwz\in L \iff uv^iwz\in L.$$

My question to you is: is there any way changing the for all $$i \ge 0$$ condition to for all $$0\le i\le N$$ for some $$N$$ - and the lemma will still be correct?

That $$N$$ may be constant, depend on the lemma's k, and so on.

I can't find an approach to prove it, any ideas?

• Try constructing a counterexample first. Jun 11 '20 at 7:34
• In the proof of the lemma in the attached paper, it seems that they only use N=1, when proving that a language is regular. When assuming a language is regular, it's easy to say that it works with i={0,1}, because then there are less things to prove. So i seems the answer to my question is true, for N=1. Have I got it wrong somewhere?
– Tom
Jun 11 '20 at 8:43
• It’s hard to say without seeing the proof. If the proof still works even when $N=1$, then the lemma holds even when $N=1$. Jun 11 '20 at 9:35

Yes, what you have observed is correct. We can, in fact, always take $$N=0$$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once.

A language $$L$$ is regular iff $$\exists k$$, $$\forall x\in \Sigma^k$$, $$\exists u,v,w\in \Sigma^*$$ such that $$x=uvw$$, $$|v|\ge 1$$ and $$\forall z\in \Sigma^*$$, $$uvwz\in L \iff uwz\in L.$$

As you have observed, the article has basically proved the above fact.

Here is a simpler proof of the "$$\Longleftarrow$$" direction. Let $$[y]$$ be the Myhill-Nerode equivalence class represented by string $$y$$. Suppose $$|y|\ge k$$.

Let $$x$$ be the first $$k$$ symbols of $$y$$ and $$t$$ be the rest of $$y$$, i.e., $$y=xt$$ and $$|x|=k$$. By assumption, there exists $$u,v,w\in\Sigma^*$$ such that $$x=uvw$$, $$|v|=1$$ and $$yz=x(tz)=uvw(tz)\in L\iff uw(tz)=(uwt)z\in L.$$ The equivalence above means $$[y]=[uwt]$$. Since $$uwt$$ is $$y$$ with $$v$$ deleted, $$|uwt|\lt |y|$$. That means the shortest string in a Myhill-Nerode equivalence class must be shorter than $$k$$.

Since there are finitely many strings that are shorter than $$k$$ symbols, there are only finitely many Myhill-Nerode equivalence classes. By the celebrated Myhill-Nerode theorem, $$L$$ is regular.

• 'the "⟸" direction' means the "only if" part of that "iff". Jun 15 '20 at 16:59
• Loved the answer, thank you!
– Tom
Jun 16 '20 at 9:03
• I have a Further question: can the "forall z" be restricted to "forall z upto length K" or any significant limitation to it (meaning that the number of possible z will be finite), and it will still imply that L is regular?
– Tom
Jun 16 '20 at 9:14
• That sounds like an interesting question. Jun 16 '20 at 13:18