5
$\begingroup$

This standard definition of 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 = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  1. $|y| \ge 1$
  2. $|xy| \le p$ and
  3. for all $i \ge 0$, $xy^iz \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: $|y| \ge 1$ and $i \ge 0$, $xy^iz$. 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 \ge 0$, i.e. effectively $|y| = 0 $. Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.

$\endgroup$
  • $\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
7
$\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.

$\endgroup$
3
$\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?

$\endgroup$
2
$\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.

$\endgroup$
  • 2
    $\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

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.