necessary and sufficient pumping lemma - bounded pumping variant

Question

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?

Answer 1

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.