1
$\begingroup$

All explanations and proofs I find about the Pumping Lemma are ambiguous. So if I understand this correctly, if we can find some $p>0$, then for any string $|w| \ge p$, we should be able to split it up into $xyz$ according to some conditions which are satisfied as shown below.

Here's the problem. Say $L$ is the language with equal number of zeros and ones. As far as I know, $L$ is considered to be irregular. But we could easily find $p$ that satisfies the conditions:

$$p=4 $$ $$xyz=0011$$ Let $y$ be the middle part $01$.

  1. $y$ can be pumped.

  2. $|y|>0$

  3. $|xy|\le p$

But what is wrong with this reasoning? It seems to satisfy all the conditions yet still this language is considered irregular.

$\endgroup$
  • 1
    $\begingroup$ The answer by Stella Biderman shows the fundamental problem with your reasoning: that a language satisfies the statement of the pumping lemma does not necessarily mean that it is regular. However, your language does not even satisfy the statement of the pumping lemma. Whatever $p$ you pick, the word $0^p1^p$ belongs to your language, is longer that $p$, but cannot be written as $xyz$ with $|xy| \leq p $ and $|y|>0$ and all $xy^nz$ still in your language, because $y$ has to consist of nothing but $0$'s. $\endgroup$ – Magdiragdag Feb 4 '16 at 20:00
  • $\begingroup$ But that's what I don't understand. What conditions dependent on p must be satisfied so we can prove a language is not regular? It seems that there are values for p that work, but others that don't work. So what exactly do we have to find to be confident that the language is not regular? I just don't get it. Is it finding p such that the conditions don't hold? But such values of p can be found for regular languages as well. So what is it? I just can't see it. What do you need in order to be able to separate irregular languages from regular ones? $\endgroup$ – Hex4869 Feb 4 '16 at 20:12
  • 1
    $\begingroup$ What I am saying is that for this particular language, you can (directly) use (this version of) the pumping lemma to show that it is not regular. My guess is that you're struggling to get the quantification over $p$ and $w$ correct in your reasoning (e.g., your phrasing 'if we can find some $p > 0$, then for any $|w|>p$ ... ' is weird; correct would be 'there exists a $p > 0$ such that for all $|w| > p$ ...') $\endgroup$ – Magdiragdag Feb 4 '16 at 20:28
1
$\begingroup$

The Pumping Lemma is a statement true of all regular languages. However, it is not necessarily false for irregular languages. In general, the Pumping Lemma is used to prove something must be irregular. It cannot be used to prove something is regular, because of exactly this example.

This is analogous to saying "9 is odd and greater than 2! Why isn't it prime?" Just because all primes greater than 2 are odd doesn't make all odd numbers a prime greater than 2.

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