# requirement for pumping lemma in regular language

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not.

This is what I have understood so far though For a regular language $L$, there exists a $p > 0$ such that for all $w ∈ L$ where $|w| ≥ p$, there exists some split $w = vxu$, for which the following holds:

$|vx| ≤ p$

$|x| > 0$

$vx^iu ∈ L$ for all $i ≥ 0$

but what is the rationale behind the requirement of $|vx| ≤ p$ what happens if we drop that requirement??

thanks ahead

-
"As I know is used to decide if a language is regular or not." - No. PL is a necessary, but not sufficient condition for the regularity of a language. So if a language does not satisfy the PL, it is not regular. But if it does satisfy the PL, then it may still not be regular. –  Guildenstern May 25 at 16:58
The constraint $|vx| \leq p$, which is necessary for the effectiveness of the lemma as showed by the answers, comes up directly out of the proof. Have you seen the proof of the pumping lemma? –  Yuval Filmus May 25 at 18:02
I am confused; you say "I understood" and then cite the lemma. Have you read (and understood) the proof? –  Raphael May 26 at 10:24

## 1 Answer

$|vx| < p$ mean that $x$ is short and it is at the beginning of $w$. If you were to remove that constraint, all regular languages would still satisfy the lemma, but more irregular ones would too. For example $L = \{a^n \mid n ~\text {is not prime}\}$, when $n = m \cdot k$ can be pumped by taking $x = a^k$.

-