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$
3
  • $\begingroup$ Try constructing a counterexample first. $\endgroup$ Jun 11, 2020 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, 2020 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$ Jun 11, 2020 at 9:35

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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