Nonregular languages that satisfy the pumping lemma at different strengths

439 Views Asked by At

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!