1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Try constructing a counterexample first. $\endgroup$ – Yuval Filmus Jun 11 at 7:34
  • $\begingroup$ 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? $\endgroup$ – Tom Jun 11 at 8:43
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jun 11 at 9:35
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 'the "⟸" direction' means the "only if" part of that "iff". $\endgroup$ – John L. Jun 15 at 16:59
  • $\begingroup$ Loved the answer, thank you! $\endgroup$ – Tom Jun 16 at 9:03
  • $\begingroup$ 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? $\endgroup$ – Tom Jun 16 at 9:14
  • 1
    $\begingroup$ That sounds like an interesting question. $\endgroup$ – John L. Jun 16 at 13:18

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.