1
$\begingroup$

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones)

The three versions are as follows: If $A$ is a regular language, then there exists a number $n$ (the pumping length), such that for any string $a \in A$ of length greater than $n$, then:

  1. Weak: $a$ can be divided into three pieces $a = xyz$ such that $|y| > 0$ and for each $i \geq 0$, $xy^iz \in A$

  2. Moderate: same as above, except we also have the condition that $|xy| \leq n$

  3. Strong: $a$ can be divided into $a = z_1z_2z_3$, and for all cases where $|z_2| \geq n$, there exists a further decomposition of $z_2 = uvw$ where $0 < |v| \leq N$ and for all $i$, $z_1uv^iwz_3 \in A$

So I have a few questions:

  1. What's an example of a nonregular language that can satisfy the weak but not the moderate pumping lemma?

  2. What's an example of a nonregular language that can satisfy the moderate but not the strong pumping lemma?

  3. What's an example of a nonregular lanugage that can satisfy the strong pumping lemma?

  4. If we let $L$ be a regular language, what can the strong pumping lemma say about strings $a \notin L$?

Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.