1
$\begingroup$

The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the constant in the pumping lemma)

https://cs.stackexchange.com/a/55606/99669

Why is this the case? The lower limit can be explained by the constant of the regular pumping lemma, because in infinite languages there exists a word in L which is longer than n.

But how comes there is an upper limit? The pumping lemma does not say anthing about a upper limit for the words we choose.

Improve this question
$\endgroup$
  • $\begingroup$ Hint: choosing $i = 0$ reduces the length of the word. $\endgroup$ – Yuval Filmus Jan 29 '19 at 16:06
  • $\begingroup$ @YuvalFilmus If we have x*y^i*z we have xz as a word, when i=0. The length of x is restricted by the condition |xy|≤n, but z is not restricted at all in the pumping lemma. Or at least not directly. I can not see a restriction, but it seems to be |z|≤n, so we get the upper limit 2n for |xz|. But why should z be restricted in length? $\endgroup$ – DisplayedName Jan 29 '19 at 16:56
1
$\begingroup$

Suppose that $L$ is an infinite language which satisfies the pumping lemma with constant $n$. Let $w \in L$ be a word of minimal length in $L \cap \Sigma^{\geq n}$ (i.e., among the words in $L$ of length at least $n$, choose a word of minimal length). Since $L$ satisfies the pumping lemma, we can write $w = xyz$ in such a way that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. In particular, $xz \in L$. Since $|xz| < |xyz|$, we must have $|xz| < n$, and so $|w| = |xz| + |y| < n + |xy| \leq 2n$.

Improve this answer
$\endgroup$
  • $\begingroup$ How do you get from $|xz| < |xyz|$ to $|xz| < n$? I can not see how this could be possible. How is there a boundary for |z|? $\endgroup$ – DisplayedName Jan 29 '19 at 17:54
  • $\begingroup$ Hint: how did we choose $w$? $\endgroup$ – Yuval Filmus Jan 29 '19 at 17:55
  • $\begingroup$ We did choose $w$ as the shortest possible word in $L$ that is still longer or equal to $n$. But how can we know that the smallest word is not very long? Like a language that produces words with one or more 1 followed by 100 times a 0. So we could use the pumping lemma with $y=1,z=$0^100 and choose $n=2$. But apparently this is not possible? I dont see why it is not, because $y$ is not the empty word, $|xy|≤2$ and all words $xy^i z$ are in $L$. $\endgroup$ – DisplayedName Jan 29 '19 at 18:03
  • $\begingroup$ My answer proves this. Try to follow the proof. $\endgroup$ – Yuval Filmus Jan 29 '19 at 18:27
  • $\begingroup$ Not quite. We have $|xz| < |xyz|$, hence $xz$ is a word in $L$ shorter than $w$. Since $w$ is a shortest word under the constraint of having length at least $n$, the words $xz$ must have length less than $n$. $\endgroup$ – Yuval Filmus Jan 30 '19 at 11:38
1
$\begingroup$

Think about it in terms of the proof of the pumping lemma.

The pumping lemma is true because, if you read a long enough word, you must visit the same state of the automaton twice, so you can go around that loop as many times as you want (including zero) and then go on to an accepting state. How long does this take? If the automaton has $n$ states, you know you must have been once around the loop after at most $n+1$ steps. From there, you need to get ot an accepting state and either you're in one already, or you need to visit at most $n-1$ more states before you get there. So the total is at most $2n$.

If that procedure results in a word of length less than $n$, just go around the loop enough times to lengthen it.

Improve this answer
$\endgroup$
  • $\begingroup$ I think the question only assumes that the pumping lemma holds, not that the language is regular. $\endgroup$ – chi Jan 30 '19 at 11:43
  • $\begingroup$ @chi In that case, the question is trivial: the pumping lemma merely says that the value $n$ exists. So just choose $n=|w|$ for some "pumpable" word and, voila!, $n\leq |w|\leq 2n$. $\endgroup$ – David Richerby Jan 30 '19 at 12:03
  • $\begingroup$ Well, we can't assume that there is a word in $L$ of length exactly $n$. We only know that, for any word $w$ in $L$ with length $\geq n$, the word $w$ must be pumpable. I think Yuval, above, only assumed this (otherwise, I agree, it's trivial). $\endgroup$ – chi Jan 30 '19 at 12:59

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.