Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
"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
3  
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
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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