1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "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. $\endgroup$ – Guildenstern May 25 '14 at 16:58
  • 3
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus May 25 '14 at 18:02
  • $\begingroup$ I am confused; you say "I understood" and then cite the lemma. Have you read (and understood) the proof? $\endgroup$ – Raphael♦ May 26 '14 at 10:24
3
$\begingroup$

$|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$.

|cite|improve this answer
$\endgroup$

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.