[Solved]: How does a regular language satisfies the second condition of the pumping lemma

Problem Detail: 

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.

Asked By : Opal Thongpetch

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38120

 Ask a Question

 Download Related Notes/Documents