2
$\begingroup$

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact structure of a proof where you show a language is not regular or context-free?

Wikipedia and most proofs start with "Suppose $L$ is a regular language", which would mean it is a proof by contradiction, because it isn't.

But the lemma has the quantifiers $\exists, \forall, \exists, \forall$ in order. And in the proof you assume a given constant given by the first $\exists$, and then you come up with some word (the first $\forall$), format it in some given substring division (the second $\exists$) and again come up with some $k$ (second $\forall$) for which you show it is not in $L$.

This seems to me like a counterexample proof ("this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma"), and not a proof by contradiction?

$\endgroup$
  • $\begingroup$ Right now, I'm tending to think of it as a proof by contradiction, where you reach a contradiction by an example. I hope that makes sense. $\endgroup$ – PHPirate Jun 6 '16 at 10:59
  • $\begingroup$ Note our reference questions on regular and context-free Pumping lemmata, among other things. $\endgroup$ – Raphael Jun 6 '16 at 11:05
  • 4
    $\begingroup$ Indeed, lots of people present it as proof by contradiction, but I tend to think of it as proof by contrapositive. The Pumping Lemma states "Regular implies Pumping" and one uses the implication "not-Pumping so not-Regular". The not-Pumping is by example, but in fact infinitely many examples, as for any length one has to find a counter-example of at least that length. Usually these examples have a strict pattern (like $a^nb^n$) and we treat them as a single string, but in the proof logic we have infinitely many of them. $\endgroup$ – Hendrik Jan Jun 6 '16 at 11:21
  • $\begingroup$ @Hendrik Jan Oh of course, there's the contrapositive! Indeed, there is a (general) example involved, so this is one good explanation. Thanks! An other explanation is the the example comes up when processing the $\forall$ in a proof by contradiction. But I like your answer better than the others. $\endgroup$ – PHPirate Jun 6 '16 at 11:59
  • $\begingroup$ @HendrikJan Hm. In order to show "not pumping" we need to assume it applies, though; then we get "not regular" directly from the contradiction, as that's our assumption. $\endgroup$ – Raphael Jun 7 '16 at 20:07
4
$\begingroup$

this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma

You are missing that in order to construct this counterexample you have to assume that $L$ is regular. Then you apply the Pumping lemma, which yields the Pumping length $p$. Only then do you construct your (counter)example string (using $p$!) and show that it contradicts the Pumping lemma. Hence, the assumption must be false.

So while you can say that you derive the contradiction using a counterexample, the outer-most proof is by contradiction.
With the assumption, you wouldn't have $p$!

Note that proofs can be nested, so you don't need to see only one proof technique. For instance, induction proofs often use a proof by contradiction inside the inductive step.

$\endgroup$
1
$\begingroup$

The formulation of the Pumping Lemma, with explicit quantifiers, is as follows:

$$\forall L\in REG, \exists p>0, \forall w\in L,|w|>p\Rightarrow \exists x,y,z\in \Sigma^*, w=xyz\wedge c_1\wedge c_2\wedge c_3$$ where $c_1,c_2,c_3$ are the conditions of the lemma.

Thus, a proof that a language is not regular is indeed by contradiction. In order to see the general structure of a proof, it is convenient to this of ourselves as trying to contradict the lemma, while an adversary is trying to prove the lemma holds.

Thus, the general structure is as follows. The lemma claims something for every regular language, so we choose a certain language we want to "attack".

Now, the adversary gets to choose $p$, so we write "for every $p>0$". Next, the lemma says something for every $w\in L$ such that $|w|>0$, so we get to pick $w$, but in order to make it useful, we need to pick $w\in L$ such that $|w|>p$ (otherwise the adversary wins vacuously).

Now, we have $\exists x,y,z$, so the adversary chooses them. We thus write "there exist $x,y,z$ such that $w=xyz$". Next, we want to show that at least one of the conditions $c_1,c_2,c_3$ does not hold. Technically, if $c_1$ or $c_2$ don't hold, then the adversary chose "stupidly", and we're done. Thus, we assume that $c_1$ and $c_2$ do hold, and we show that $c_3$ (the pumping argument) fails, and thus we win.

So overall we get the following proof structure:

Assume by way of contradiction that $L\in REG$, then let $p>0$ be its pumping constant. Consider the word $w=...$(something clever). Let $x,y,z\in \Sigma^*$ such that $w=xyz$, and $|xy|\le p$, and $|y|>0$, we show that there exists $i\ge 0$ such that $xy^iz\notin L$, in contradiction to the pumping lemma.

Thus, $L\notin REG$.

$\endgroup$
  • $\begingroup$ Thanks for the general explanation, but I'm still not sure why my reasoning that this is a counterexample, maybe even inside a contradiction, is wrong? Or maybe is it essentially the same, since you provide a contradiction by counterexample? $\endgroup$ – PHPirate Jun 6 '16 at 10:54
  • $\begingroup$ Perhaps you view the "pumped word" as a counterexample. It can indeed be thought of as a counterexample to the claim that every word has a decomposition according to the lemma. But it's not a "counterexample to the language being regular". $\endgroup$ – Shaull Jun 6 '16 at 13:03
1
$\begingroup$

In general, proving things is a creative enterprise. As such, there is no "standard template": you're free to do whatever you want, as long as it's logically valid.

In particular, as long as you understand why a proof works, you shouldn't worry too much about whether it's a proof by contradiction, or a proof by counterexample, or something else. That's a bit like a poet wondering whether a particular phrasing they've used is a zeugma or a syllepsis. As long as it's effective imagery, who cares except the critics?

$\endgroup$
  • $\begingroup$ That's what I'm trying to find out, why and how the logic is valid here. $\endgroup$ – PHPirate Jun 6 '16 at 10:57
  • $\begingroup$ @PHPirate The logic of what? You've not quoted any proof so I can't tell what logic you're asking about. $\endgroup$ – David Richerby Jun 6 '16 at 11:51

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.