3
$\begingroup$

I'm a little bit confused about the second condition of the pumping lemma which are:

  1. $|y|\geq1$
  2. $|xy|\leq p$
  3. $\forall i \geq 0:xyiz\in L$

I don't understand why the length of substrings $xy$ has to be less than the pumping length ? Considering the example below:

Suppose we have a language $L = \{ w | w ∈ 1^*0+1^*\}$ and a string $s \in L$ which $L$ is a regular language.

Let the string $s = 101$ and $S$ can be split into three substring $xyz$ where $y$ can be pumped.

Therefore:

$x = \text{'1'}$ $y=\text{'0'}$ and $z=\text{'1'}$. It seems that substring $|xy|$ is somehow larger than the pumping length $p$ itself (in this case: $p=1$ since there's only one $0$), Therefore $|xy| > p$, a contradiction ! Does this mean that the language $L$ in this case is not regular ?

Or did I misunderstood something.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Feb 8 '15 at 18:44
5
$\begingroup$

The pumping lemma states that if a language $L$ is regular then there exists $p$ such that every word $w \in L$ can be split as $w = xyz$ such that

  1. $|y| \geq 1$.
  2. $|xy| \leq p$.
  3. For all $i \geq 0$, $xy^iz \in L$.

You give an example of a language $L$ and a string $s \in L$ which can be split as $s = xyz$ such that

  1. $|y| \geq 1$.
  2. $|xy| = 2$.
  3. For all $i \geq 0$, $xy^iz \in L$.

This is a property which is similar to the one guaranteed by the pumping lemma, but perhaps different. The property expressed by the pumping lemma need not be the only property satisfied by a regular language. All the pumping lemma states is that if a language is regular then it satisfies the pumping property. It does not state that if a language is regular then the only property it satisfies is the pumping property.

To give an analog, consider the following statement: if $x$ is a multiple of $4$ then it is a multiple of $2$. Here is a "counterexample": $12$ is a multiple of $4$, but it is a multiple of $3$ (rather than $2$). Your counterexample is similar.

Another issue is the pumping length $p$. If you look at the proof, then $p$ is the size of a DFA accepting $L$. In particular, $p$ doesn't depend on $w$. In your case, it's not clear why you assume that $p=1$; in fact, when applying the pumping lemma, you cannot assume anything about $p$. You're just guaranteed that some $p$ exists. In fact, for your language $p \geq 5$, since the minimal DFA has $5$ states.

The condition $|xy| \leq p$ is supposed to help you apply the pumping lemma. For example, if you look at the language $0^n1^n2^m$, without this condition you wouldn't be able to prove that the language is not regular, since the pumped part could always be in the $2^m$ area. The condition $|xy| \leq p$ allows you to locate the pumped part.

This condition isn't always general enough, for example it doesn't work for showing that $2^m0^n1^n$ is not regular. There is a more general version of the pumping lemma which can handle this called Ogden's lemma.

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