6
$\begingroup$

This statement of the pumping lemma from Wikipedia.

Let $L$ be a regular language. Then there exists an integer $p \ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = x y z$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  1. $\lvert y \rvert \ge 1$
  2. $\lvert x y \rvert \le p$ and
  3. for all $i \ge 0$, $x y^i z \in L$.
    $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

What confuses me about the definition of pumping lemma are two requirements: $\lvert y \rvert \ge 1$ and $i \ge 0$, $x y^i z$. The way I read it, that we are required to have $y$ length be equal to one or greater, and at the same time, we can completely skip it, since $i \ge 0$, i.e. effectively $\lvert y \rvert = 0 $. Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.

$\endgroup$
  • 1
    $\begingroup$ Can the source of the confusion be the fact that when using the pumping lemma you don't get to choose x,y,z, but you do get to choose i? $\endgroup$ – Boris Trayvas Jun 13 '12 at 9:41
  • $\begingroup$ This is a mistake I have done myself. The pumping lemma is a tool to prove a language is NOT regular. As Dave Clarke mentioned, if the language is indeed regular, $xz$ is in the language, since you can just "skip" the loop $\endgroup$ – chazisop Jun 13 '12 at 14:47
  • $\begingroup$ You have a finite state machine. The string y is a string that goes from one state S back to the state S. Then it doesn't matter whether you repeat y 0 times, 1 time, 2 times or a trillion times. You still end up in S. $\endgroup$ – gnasher729 Feb 10 at 19:31
  • $\begingroup$ One thing is the string $y$, and it's length $\lvert y \rvert$, another one is $y^i$, which is "repeat $y$ $i$ times". You can certainly repeat a short string never (0 times) or a lot of times ("bla bla bla"...). $\endgroup$ – vonbrand Feb 15 at 16:28
8
$\begingroup$

Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state $q$ to state $q$ consuming word $y$ – that is, $y$ is the word based on the symbols on the transitions going from $q$ back to $q$.

The pumping lemma says, more or less, that you can get to such a state $q$ from the initial state by consuming the word $x$ and that you can get to the final state from state $q$ by consuming the word $z$. In the middle you can go through the loop as many times as you like. Thus making the complete word $xy^iz$, where $i$ is the number of times you chose to go through the loop.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

"The way I read it, that we are required to have $y$ length be equal to one or great, and at the same time, we can completely skip it, since $i\geq 0$, i.e. effectively $|y|=0$."

If $y$ had length $0$, then it would be the empty word, and so it would not be useful that we can skip it (or pump it as many times as we like). The condition $|y|\geq 1$ is insuring that there is a nontrivial word that can be pumped.

Does that help?

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The condition that $y$ has length at least one is to avoid a triviality. If you allow the length of $y$ to be zero then for any language you can divide each word in the language into $xyz$, such that $xy^iz$ is still in the language; choosing an empty $y$ means $xyz = xy^iz$ for any $i$.

Thus the ability for a language to be "pumped" with this alternate version of the pumping lemma tells us nothing about the language. The only language that couldn't be so "pumped" is the empty language, and even then that's because it simply contains no words.

Observing that $i = 0$ is one of the values of $i$ does not make $|y|$ "effectively" 0. At the point that you're considering all values of $i$ you're talking about some particular $y$; (the one that can be found for the language and word under consideration). Thus taking $i = 0$ produces a different string $w$ by removing $y$, which is completely different from dividing $w$ up into $xyz$ where $y$ is empty.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ "The only language that couldn't be so "pumped" is the empty languag" -- technically, $\emptyset$ can be pumped: "for all words longer than..." is certainly true. $\endgroup$ – Raphael Jun 20 '12 at 9:32
0
$\begingroup$

The lemma states that all strings longer than $p$ can be subdivided into $x y z$ with $\lvert x y \rvert \le p$ and $y \ne \epsilon$ so that for all $i \ge 0$ $x y^i z$ belongs to the language. This means that $0 < \lvert y \rvert \le p$, obviously. If you take a "pumped" string, i.e. $x y^i z$ for $i > 1$, the resulting string is longer than $p$ and thus can be pumped. Again, plain $y$ works just as before, giving $x y^{i + j} z$, for $i + j > 1$, and that you knew.

The lemma states there is some subdivision, it doesn't say there is just one. There may very well be several.

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